Файл: Курсовая по электротехнике (Марсова) .doc

П5.3. Конечные автоматы

Ранее отмечалось, что если блок обратной связи обобщенной структурной схемы (см. рис. П5.1) последовательностного устройства содержит элементы памяти, например триггеры, то полученная структура является конечным автоматом. Термин «конечный» означает, что число выходных сигналов, и, следовательно, состояний автомата, является ограниченным. Введем понятие состояния автомата. Это понятие уже вводилось ранее для одиночного триггера и под ним понимался выходной сигнал триггера. В общем случае, блок обратной связи автомата может содержать несколько триггеров. Поэтому под состоянием понимается сигнал, формируемый на выходе блока обратной связи. С учетом сказанного обобщенную структурную схему конечного автомата можно представить в виде двух подсистем: комбинационной и триггерной или подсистемы памяти. В отличие от ранее рассмотренной, приведенная структура предполагает наличие еще одного сигнала. Это сигнал синхронизации С, используемый для инициализации переключения элементов памяти (триггеров) подсистемы памяти.

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

П5.4. Описание поведения цифрового автомата

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

Граф переходов представляет графическую интерпретацию алгоритма работы цифрового автомата. Он наиболее удобен для формализации алгоритма его работы. При построении графа переходов каждому состоянию автомата ставится в соответствие некоторая вершина графа, а переход из одного состояния в другое соответствует направленному ребру, соединяющему начальное и конечное состояния. Причем каждое ребро взвешено, т. е. над ним указывается дробь, числитель которой указывает значение входного сигнала, под действием которого осуществляется указанный переход, а знаменатель соответствует текущему значению выходного сигнала автомата Z[(m– 1)…0].

Таблица состояний включает G+ 1 столбец истрок, гдеG– число различных входных сигналовХ[(n1)…0], которые могут присутствовать на входе автомата. В первом столбце перечисляются все возможные состояния автомата (состояния S_n). Остальные столбцы соответствуют возможным входным сигналам. На пересеченииi-ой строки, соответствующей текущему состоянию автомата (соcтояниеS_i) иj-го столбца, соответствующего текущему значению входного сигнала (сигналХ(j) записывается дробь, числитель которой показывает следующее состояние автомата (S_{n+ 1}), а знаменатель – текущее значение выходного сигналаZ.

П5.5. Алгоритм синтеза цифрового автомата

1. Исходя из условий функционирования, определяют число необходимых состояний и требуемый объем памяти цифрового автомата. Число необходимых для реализации состояний определяется как наибольшее значение выходных кодов устройства, формируемых при одном значении входного сигнала. Объем памяти триггерной подсистемыопределяется из условия, чтоnразрядный двоичный код может приниматьразличных значений. Тогда требуемый объем памяти, т. е. число необходимых триггеров подсистемы памяти определяется из условия:

где функция CEILозначает округление до ближайшего большего целого.

2. Выполняют формальное описание алгоритма работы автомата.

3. Выбирают тип триггера для реализации подсистемы памяти.

4. Используя формальное описание алгоритма работы автомата и таблицу переходов выбранного типа триггеров, составляют расширенную таблицу истинности, характеризующую работу комбинационной подсистемы автомата. Число строк этой таблицы равно максимальному числу входных сигналов, действующих на входе комбинационной подсистемы. В столбцах таблицы записывается следующая информация: Х[n-1…0] – вхо­дной сигнал; S_n[q-1….0] – текущее состояние автомата; S_n+1[(q-1)…0] – последующее состояние автомата; Y[k-1…0] –cигнал ПОС;Z[m-1…0] – выходной сигнал автомата.

5. Используя расширенную таблицу истинности, минимизируют ФАЛ, описывающие работу комбинационной подсистемы автомата.

6. Используя полученные ФАЛ, синтезируют логическую схему цифрового автомата.

Проиллюстрируем описание алгоритма работы автомата на примере.

Пример П5.1. Спроектировать устройство, формирующее на выходе следующие последовательности выходных кодов:

 при входном сигнале X = 1: 000, 001, 010, 100;

 при входном сигнале Х= 0: 100, 010, 001, 000.

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

1. Из заданного алгоритма работы следует, что при одном значении входного сигнала Хна выходе автомата может формироваться 4 кода. Следовательно, число необходимых состояний автомата. Для реализации такого числа состояний достаточно двух триггеров.

2. Синтезируем граф переходов, соответствующий заданному алгоритму. Обозначим состояния автомата окружностями и обозначим их как S0,S1,S2 иS3.

Используя граф переходов, составим таблицу состояний для заданного алгоритма. В таблице состояний обозначено S0 = 00,S1 = 01,S2 = 10,S3 = 11.

Таблица П5.1. Таблица состояний для заданного алгоритма

Sn	X= 1	X = 0
00	01/000	11/100
01	10/001	00/000
10	11/010	01/001
11	00/100	10/010

3. Для реализации триггерной подсистемы можно использовать любой тип синхронного триггера, изменяющего своё состояние по фронту импульса сигнала синхронизации. Используемый тип триггера приведет к изменению схемы комбинационной подсистемы автомата. Можно сформулировать некоторые общие закономерности выбора типа используемого триггера. При выборе триггера, управляемого двумя управляющими сигналами (RS-иJK-триггера) увеличивается разрядность сигнала ПОС, однако, как правило, упрощается схема комбинационной подсистемы.

4. Составим расширенную таблицу истинности.

Таблица П5.3. Расширенная таблица истинности заданного алгоритма

Поясним составление расширенной таблицы истинности. В первых двух столбцах таблицы фактически записаны все комбинации возможных входных сигналов комбинационной подсистемы автомата. Это входные сигналы Хи сигналы, формируемые подсистемой памяти в данный момент времени. Очевидно, что сигналS_nопределяется комбинацией выходных сигналов триггеров подсистемы памяти, т. е., гдеиQ₀выходные сигналы триггеров под номерами 1 и 0.

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

Четвертый столбец содержит сигналы ПОС, которые должна формировать комбинационная подсистема для обеспечения заданного порядка переключения триггеров подсистемы памяти. Подсистема памяти в нашем случае состоит из двухТ-триггеров, поэтому сигналдвухразрядный, гдеисоответственно управляющие сигналы первого и нулевого триггеров подсистемы памяти. Значения этих сигналов можно получить из таблицы переходов выбранного типа триггера (см табл. П5.2). Например, для первой строки расширенной таблицы истинности имеем ит. е. оба триггера должны переключиться. Из таблицы П5.2 имеем, что для перехода триггера из сброшенного состоянияв состояние установкина его управляющий вход необходимо подать управляющий сигнал. Поэтому сигналYдля этой строки равен 11.

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