Структурный синтез автоматов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Структурный синтез автоматов

Если проанализировать структурную схему рис. 58 и результаты абстрактного синтеза автоматов на основании ГСА, то становится ясно, что СА - это одна или две независимые комбинационные схемы F₁ в момент t и F₂ после сигнала ф, т.е. в момент t + 1.

Память автомата нужна для того, чтобы разнести во времени сигналы Z_i(t), соответствующие состоянию автомата a_i(t) в момент t, и те же сигналы по обратной связи Z_i(t + 1), т.к. сигналы Z_i являются входными для схемы СА в момент t, и по сигналу ф формируются выходные значения Z_i, которые снова нужно подать на вход СА по обратной связи для определения кода Z нового состояния a (t + 1). Без наличия памяти в обратной связи автомат не будет устойчиво работать, т.к. для одних и тех же значений сигналов {б} за время сигнала синхронизации ф, при достаточном быстродействии схемы СА может произойти многократная смена состояний, а необходима только одна.

Разнесение во времени сигналов Z(t) и Z (t + 1) возможно осуществить двумя способами:

– включением в обратную связь элементов задержки (временная реализация функции памяти);

– включением в обратную связь регистров памяти с записью по сигналу t и считыванием по сигналу (t + 1).

В интегральной схемотехнике первый способ практически не применяется.

Организация памяти автоматов

а) При малом числе состояний автомата (N < 12) для каждого состояния a(t) предусмотрим независимый триггер Z(t). Тогда переход из одного состояния в другое приведет к тому, что триггер Z, установленный в состояние 1 в момент t, в момент (t + 1) будет приведен в состояние «0», а в момент (t + 1) будет приведен в состояние «1».

Т.е. для представления памяти автомата потребуется столько триггеров, сколько состояний в автомате (для данного примера i = ), и переменные Z будут совпадать со значениями состояний a_i (i = ).

Однако поскольку необходимо разносить во времени Z(t) и Z (t + 1), то для реализации памяти автомата потребуется 2N триггеров, ведь не исключена ситуация перехода a_i(t)>a_i(t + 1), когда автомат снова должен вернуться в тоже состояние (например из2го снова во второе) при некоторых условиях.

Такой способ кодирования номеров состояний автомата называется унитарным (Unit - т.к. каждому десятичному номеру состояния соответствует независимый элемент памяти (код с одной «1»).

б) Двоичное кодирование номеров состояний в памяти автомата.

При числе состояний N > 12 число триггеров, равное 2N, становится большим. Затраты элементов памяти и логических схем «И» для передачи кодов Z₁, Z₂, …, Z_p(t) становятся неприемлемыми для экономичной реализации. В этом случае номера состояний автомата представляются двоичными кодами в виде ДПК или ДКГ. Тогда число триггеров P при N состояниях a(t) определится из соотношения:

2^P ? N, т.е. p = Int(log₂N), где Int обозначает целую часть числа. Для приведенного примера N = 10, следовательно, p = 4, и память автомата есть два четырехразрядных регистра с парафазной связью между ними.

Т.е. вместо Z₁, Z₂, …, Z₉ в случае унитарного кодирования для ДПК (и для ДКГ) потребуется всего 4 переменных Z₀, Z₁, Z₂, Z₃ рис. 59. Следовательно, число триггеров с 18 снизится до 8.

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

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

Память быстродействующих автоматов. При организации памяти на двух последовательно соединенных регистрах а(t) и a (t+1) автомат работает по двухтактной схеме (ф и ). Но ведь полезной функцией автомата являются не его внутренние переходы из состояния в состояние, а генерация выходных сигналов с₁, с₂,…, с_k (или А_l, A₂,…, A_k) в определенной логической взаимосвязи и временной последовательности.

О.Ф. Лобов и Н.А. Гасников [23] предложили параллельную организацию (рис. 60) памяти, позволяющую генерировать выходные микрооперации как по сигналу ф, так и по , сохраняя при этом временную последовательность переходов a(t) и a (t + 1). Для этого используются два параллельно работающих регистра, выходы которых объединены схемами «ИЛИ», т.е. по входам комбинационных схем работа производится как бы от единого регистра памяти. Синхронизация в параллельных блоках перекрестная: считывание кода происходит по синхроимпульсу ф с первого регистра памяти, а со второго - по сигналу . Пусть в Pг1 код a(t) через сборку схем «ИЛИ» передан на комбинационные блоки в этот же временной промежуток (ф). Найденное значение a (t + 1) запишется в Рг2, а по сигналу Pг1 и Рг2 изменяют свою функцию на противоположную, т.е. в Pг1 окажется a (t + 1), а считывание a(t) произойдет с Рг2. Такая организация памяти позволяет повысить быстродействие МПА в два раза на той же элементной базе.

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

На рис. 60 буквами F₁ и F₂ обозначены комбинационные схемы для реализации соответствующих систем булевых функций, т.е. комплекс F₁F₂ и есть та схема СА, которая представлена на рисунке.

сигнал унитарный автомат память

Блок с буквой Ш представляет собой шифратор для того случая, когда F₂ реализует функции формирования унитарных кодов f₀, f₁, …, f₉, а в Pг1 и Pг2 производится запись Z₀, Z₁, Z₂, Z₃ в ДПК.

Память автомата на счетчике. В большинстве случаев в графе переходов автомата можно выделить замкнутый контур с последовательным чередованием номеров состояний. Для примера на рис. 59 такой контур образуется последовательностью вершин графа с номерами 0, 1, …, 8. Номер следующего состояния определяется из выражения а (t + 1) = а(t) + 1 или а (t + 1) = а(t) + 1. Символ «~» над б показывает, что может быть записано значение как б, так и . Вне этого контура лежат переходы

.

Следовательно, если в качестве одного из регистров памяти автомата взять счетчик, то всегда, когда функция R = f₀ + f₁ + f₂ + f₅ равна 1, необходимо использовать счетчик как регистр памяти состояния а(t) с переносом кода из регистра a (t + 1) по сигналу . Но если функция R = 0, то эта «связь» должна быть прервана, т.к. достаточно прибавить 1 к счетчику для изменения (увеличения) номера его состояния. Может также использоваться универсальный счетчик, работающий как на сложение, так и на вычитание. Очевидно, что этот более сложный случай должен быть рассмотрен отдельно и подробно.

В этом случае реализация функций при наличии счетчика вместо регистра может быть «экономически» более оправданной по сравнению с вариантом реализации функций F₂ без счетчика.

Размещено на Allbest.ru