10

Оглавление

Введение 2

1 Преобразование информации с помощью автоматов 3

2 Синтез автомата Мура 7

3 Синтез автомата Мили 14

Литература 19

Приложение 20

Варианты заданий 20

Введение

Данная разработка представляет собой методическое пособие по дисциплине «Электронные промышленные устройства» — одному из важнейших компонентов федерального государственного образовательного стандарта по направлению «Электроника и микроэлектроника». Изучение этой дисциплины основано на знаниях полученных студентами в процессе изучения на ранних курсах схемотехники и системотехники. Дисциплина позволяет формировать знания и умения, необходимые для корректной постановки и решения проблем в области информатики, схемотехники при создании вычислительных структур, алгоритмов и программ обработки информации.

Работы в области теории автоматов начались в середине 50-х годов прошлого века. Моделирование конечного автомата при разработке устройств в области информатики и других областях инженерной деятельности является удобным средством, позволяющим разработчикам реализовывать алгоритмы работы в схемотехнические решения.

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

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

1 Преобразование информации с помощью автоматов

Преобразование информации в виде вход выходзависит не только от входной информации, но и от предыстории преобразования. Например, один и тот же вход — извинения пассажира после того, как он наступил другому пассажиру на ногу в троллейбусе — вызовет у него одну реакцию в первый раз и совсем другую — в третий или четвертый раз. Реакция пассажира будет различной и будет зависеть от предыдущих событий и от входной истории. Таким образом, существуют функциональные преобразователи информации, в которых выходной сигнал зависит не только от входного сигнала в данный момент, но и от входной истории [1].

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

Блок памяти автомата хранит информацию о текущем состоянии Q, а следующее состояние определяется входным сигналом U и текущим состоянием, а выходная реакция автомата обозначена V. Блок F на основе входных сигналов и предыдущих состояний формирует очередное состояние Q.

Из выше отмеченного следует, что автоматный преобразователь или управляющий автомат определяется:

1. Множеством выходных сигналов

V= {V1, V2, …, Vm},

соответствующих множеству состояний автомата. При Vi =1 исполняется i-я микрооперация.

2. Множеством входных сигналов

U = {U1, U2, …, Un},

соответствующих входной истории.

3. Множеством подлежащих реализации микропрограмм.

4. Множеством состояний

Q = {Q0, Q1, …, Qr},

Таким образом, мы имеем дело не с функциональными преобразователями информации, а с преобразователями, в которых реакция или выходной сигнал зависит не только от входа в данный момент, но и от входной истории (предыдущего состояния).

Автоматный преобразователь может быть задан как автомат Мура

Q(t+1) = A[Q(t), U1(t), U2(t), … Un(t)];

V1(t) = B1[Q(t)];

………………………………………….

Vm(t) = Bm[Q(t)];

или автомат Мили

Q(t+1) = A[Q(t), U1(t), U2(t), … Un(t)];

V1(t) = B1[Q(t), U1(t), U2(t), …, Un(t)];

………………………………………...

Vm(t) = Bm[Q(t), U1(t), U2(t), …, Un(t)].

A и B функции переходов и выходов определяются заданной микропрограммой.

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

Q(t+1) = A[Q(t), U1(t), U2(t), …, Un(t)],

где Q(t) — предыдущее состояние автомата,

Q(t+1) — следующее состояние,

Существуют два основных метода построения логики управляющих автоматов.

1. Управляющий автомат с «жесткой» или схемной логикой. В этом методе каждой операции строится набор комбинационных схем. Чтобы изменять алгоритм работы автомата необходимо каждый раз изменять набор комбинационных схем.

2. Управляющий автомат с хранимой в памяти логикой (с запоминаемой или программируемой логикой). Здесь каждой выполняемой в цифровом устройстве операции ставится в соответствие совокупность хранимых в памяти микрокоманд.

Структурная схема автомата с «жесткой» логикой приведена на рис. 2

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

От блока синхронизации сигналы поступают на счетчик тактов, на выходе которого в двоичном коде представлены номера тактов от 1 до n. Дешифратор тактов формирует на j-м выходе сигнал при i-м состоянии счетчика тактов (во время i-го такта). Дешифратор кода операции выдает сигнал на j-м выходе, при исполнении j-той команды. Логические схемы и формирователи управляющих сигналов вырабатывают управляющие сигналы для выполнения требуемых в данном такте микроопераций.

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

Рассмотрим синтез и работу автоматов Мура и Мили.