ПТЦА - Прикладная теория цифровых автоматов - реферат

P_c = X ₁ X ₂ +X ₁ P_m +X ₂ P_m

Полученная система булевых функций представлена в базисе И, ИЛИ, НЕ. Соответствующая ей КС приведена на рисунке 4.

Полученную комбинационную схему можно упростить, вынеся за скобки общие части в выражениях для S и Р_c , однако существенного результата это не даст (желательно самостоятельно в этом убедиться).

Значительно упростить схему можно, если воспользоваться другим базисом, например логическим элементом "ИСКЛЮЧАЮЩЕЕ ИЛИ". В этом случае выражение для S можно записать S = (X₁ +X₂ + Р_m )mod2= X₁ Å X₂ Å Р_m . Тогда схема для S будет иметь вид (рис.3).

Иногда для синтеза КС с несколькими выходами может использоваться следующий приём. Будем считать, что при синтезе схемы сумматора функция S является функцией четырёх переменных: S=f(X ₁ ,X ₂ ,Р_m ,Р_с ). Таблица истинности для этого случая принимает вид изображенный в таблице 2.

Неопределённые значения для S соответствуют наборам, которые никогда не могут быть в реальной схеме. Карта Карно для функции S=f(X ₁ ,X ₂ ,P_m ,P_c ) представлена на рис.5.

В результате минимизации, получается :

Сравнивая выражения (2) и (3) , отмечаем, что функция S=f(X ₁ ,X ₂ ,P_m ,P_c ) проще, чем функция S=f₁ (X ₁ ,X ₂ ,P_m ). Схему, соответствующую (3) , предлагается построить самостоятельно.

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

1.2. Характеристики комбинационных схем.

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

Сложность (цена) по Квайну определяется суммарным числом входов логических элементов в составе схемы.

При такой оценке единица сложности – один вход логического элемента. Цена инверсного входа обычно принимается равной двум. Такой подход к оценке сложности оправдан по следующим причинам:

- сложность схемы легко вычисляется по булевым функциям, на основе которых строится схема: для ДНФ сложность схемы равна сумме количества букв,(букве со знаком отрицания соответствует цена 2), и количества знаков дизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения.

- все классические методы минимизации булевых функций обеспечивают минимальность схемы именно в смысле цены по Квайну.

Практика показывает, что схема с минимальной ценой по Квайну обычно реализуется наименьшим числом конструктивных элементов – корпусов интегральных микросхем.

Быстродействие комбинационной схемы оценивается максимальной задержкой сигнала при прохождении его от входа схемы к выходу, т.е. определяется промежутком времени от момента поступления входных сигналов до момента установления соответствующих значений выходных. Задержка сигнала кратна числу элементов, через которые проходит сигнал от входа к выходу схемы. Поэтому быстродействие схемы характеризуется значением r t , где t - задержка сигнала на одном элементе. Значение r определяется количеством уровней комбинационной схемы, которое рассчитывается следующим образом. Входам КС приписывается уровень нулевой . Логические элементы, связанные только со входами схемы относятся к уровню ПЕРВОМУ. Элемент относится к уровню k , если он связан по входам с элементами уровней k -1, k -2, и т.д. Максимальный уровень элементов r определяет количество уровней КС, называемое рангом схемы . Пример определения ранга r схемы приведён на рисунке 6.

Как известно, любая булева функция может быть представлена в ДНФ, которой соответствует двухуровневая комбинационная схема. Следовательно, быстродействие любой КС в принципе можно довести до 2t.

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

1.3. Системы (серии) логических элементов и их

основные характеристики.

При построении КС устройств вычислительной техники используются различные логические элементы, которые должны согласоваться по входным и выходным сигналам, напряжению питания и т.д. Для этой цели логические элементы объединяют в серии.

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

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

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

В большинстве современных серий элементов имеются микросхемы малой степени интеграции (ИС до 100 элементов на кристалл), средней степени (СИС – до 1000 элементов на кристалл), большой степени интеграции (БИС – до 10000 элементов на кристалл) и сверхбольшой степени интеграции (СБИС – более 10000 элементов на кристалл). Логические элементы в виде ИС реализуют совокупность простых логических операций: И, ИЛИ, И-ИЛИ, И-НЕ, ИЛИ-НЕ и т.д. Логические элементы на СИС и БИС реализуют узлы ЭВМ, на СБИС – микроЭВМ.

Основными параметрами серии логических элементов являются:

- питающие напряжения и сигналы для представления логического 0 и логической 1;

- коэффициенты объединения по входу;

- нагрузочная способность (коэффициент разветвления по выходу);

- помехоустойчивость;

- рассеиваемая мощность;

- быстродействие.

Серия элементов характеризуется количеством используемых питающих напряжений и их номинальными значениями. Обычно логическому 0 соответствует низкий уровень напряжения, а логической 1 – высокий. Для наиболее часто используемых серий напряжение питания составляет +5В, уровень логической единицы 2,4-5В, уровень логического 0 – 0-0,4В.

Коэффициент объединения по входу (К_об ) определяет максимально возможное число входов логического элемента, иными словами, функцию скольких переменных может реализовать этот элемент. Обычно К_об принимает значение от 2 до 4, реже К_об =8. Увеличение числа входов связано с усложнением схемы элементов и приводит к ухудшению других параметров – помехоустойчивости, быстродействия и т.д.

Коэффициент разветвления по выходу (К_раз ) показывает на сколько логических входов может быть одновременно нагружен выход данного логического элемента. Обычно К_раз для наиболее часто используемых серий равен 10. Иногда вместо К_раз задается предельно допустимое значение выходного тока логического элемента в состоянии 0 или 1.

Помехоустойчивость – это способность элемента правильно функционировать при наличии помех. Она определяется максимально допустимым напряжением помехи, при котором не происходит сбоя в его работе. Обычно это напряжение порядка 0,6-0,9 В.

Быстродействие логических элементов является одним из важнейших параметров и характеризуется временем задержки распространения сигнала. Этот параметр существенно зависит от технологии изготовления микросхем и лежит в диапазоне от единиц до сотен наносекунд.

Наиболее часто употребляемые типы интегральных микросхем – это потенциальные элементы транзисторно-транзисторной логики (ТТЛ) - серии К155, К555, К531, К1533 и т.д., транзисторной логики с эмиттерными связями (ЭСТЛ) – это серии К500,К1500, элементы на КМОП транзисторах - серии К176, К561,К564 и т.д.

При синтезе КС на реальных логических элементах необходимо обязательно учитывать ограничения на К_об и К_раз .

1.4. СИНТЕЗ КС С УЧЕТОМ ОГРАНИЧЕНИЙ НА .

При построении КС может оказаться, что выход k - го логического элемента нагружен входов других ЛЭ (рис.7а). Это означает, что k - тый логический элемент перегружен и необходимо принять меры, устраняющие указанное явление. Существуют два способа обеспечения заданного :

· использование дополнительных развязывающих усилителей;

· дублирование перегруженного элемента.

Схема с использованием дополнительных развязывающих усилителей представлена на рис.7.б. Количество p дополнительных усилителей, необходимых для обеспечения заданного , определяется по формуле:

Недостаток рассматриваемого способа в том, что в цепь распространения сигнала вносится дополнительная задержка, что не всегда допустимо.

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

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

1.5. СИНТЕЗ КС С УЧЕТОМ ОГРАНИЧЕНИЯ НА .

Представлению функции в виде ДНФ соответствует двухуровневая КС (если считать, что на ее вход могут поступать как прямые так и инверсные входные сигналы), на первом уровне которой элементы И , а их выходы объединяются на втором уровне элементом ИЛИ . Такое построение КС обеспечивает ее максимальное быстродействие, так как ранг схемы минимален. Однако, не всегда возможно на первом уровне и, особенно, на втором выбрать логические элементы с требуемым , т.к. может оказаться, что ЛЭ с таким не выпускаются промышленностью. В этом случае необходимо с помощью нескольких элементов с меньшим получить эквивалент с большим либо, что предпочтительней, преобразовать БФ, перейдя от ДНФ к скобочной форме. Этот переход сопровождается уменьшением логических элементов, требуемого для построения схемы. Осуществить такой переход можно с помощью факторного алгоритма , суть которого рассмотрим на примере.

Пусть задана некоторая булева функция в виде

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

С помощью факторного алгоритма получим скобочную форму для заданной функции. Для этого обозначим все конъюнкции буквами:

и будем рассматривать их как некоторые множества. Находим попарные пересечения множеств:

, , , , , .

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

.

Обозначим F = и находим пересечения:

, , .

Следовательно, для исходной функции имеем:

.

Обозначим ,

Пересечение . Следовательно, окончательно имеем:

Для реализации функции по последнему выражению необходимо 5 элементов 2И, 1 элемент 3И, 3 элемента 2ИЛИ ( рис.8 ).

Как видно из полученной схемы для ее реализации необходимы элементы с = 2 или 3 (в отличие от исходной с = 4 или 5). Однако ранг схемы увеличился до 7, что приводит к увеличению задержки срабатывания схемы.

1.6. Анализ комбинационных схем.

Задачи анализа КС возникают при необходимости проверить правильность синтеза (на этапе проектирования) или определить БФ, реализуемую КС (при анализе или ремонте схем). Все существующие методы анализа делятся на прямые и косвенные .

В результате анализа КС прямым методом получается множество наборов входных переменных, обеспечивающих заданное значение на выходе, что позволяет записать в алгебраическом виде БФ, реализуемую схемой. К прямым методам относится метод p- алгоритма.

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

Все упомянутые методы анализа являются машинoориентированными, что позволяет выполнить анализ схемы на ЭВМ.

Для всех методов анализа необходимо описать схему в виде схемного списка, в который включается в общем случае следующие данные: номер ЛЭ в схеме; логическая функция, реализуемая ЛЭ; входные переменные для данного ЛЭ. Например, схема представленная на рис.9, может быть описана следующим списком:

1.7. Анализ комбинационных схем методом p -алгоритма.

При данном методе, как упоминалось выше, ищутся наборы входных переменных, обеспечивающих заданное значение на выходе КС. Наборы, обеспечивающие на выходе КС логическую 1, образуют так называемое единичное покрытие . Аналогично, входные наборы, обеспечивающие на выходе КС логический 0, образуют нулевое покрытие . Рассмотрим покрытия и для простейшего логического элемента 2И, выполняющего функцию Y=X₁ X₂ . Таблица истинности для этой функции:

Табл.3 Таблица истинности функции Y=X₁ X₂

Как видно из приведенной таблицы только при единственном наборе X₁ =1 и X₂ =1 на выходе ЛЭ будет 1, т.е. единичное покрытие включает только один набор ={1 1}. На выходе ЛЭ будет 0 при трех наборах, образующих нулевое покрытие:

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

Т.о. для ЛЭ 2И можно сказать, что 1 на его выходе будет только при обеих единицах на входах, а для обеспечения 0 на выходе достаточно подать хотя бы на один вход 0. Рассуждая аналогично, получим таблицу покрытий и для основных ЛЭ, представленных ниже в табл. 4.

Таблица 4.

ЛЭ Y Y Y Y Y Y Y

НЕ 2И 2И – НЕ 2ИЛИ 2ИЛИ–НЕ ИСК. ИЛИ 3И – НЕ

X X₁ X₂ X₁ X₂ X₁ X₂ X₁ X₂ X₁ X₂ X₁ X₂ X₃

1 0 X 1 1 0 0 1 X 0 0 1 1 1

X 0 X 1 1 1

0 1 1 0 X 1 X 0 0 0 1 0 X X

X 0 X 1 1 0 X 0 X

X X 0

При анализе схемы методом p - алгоритма, задавшись определенным значением на выходе, заменяют его соответствующим покрытием элемента, формирующего выходной сигнал. В результате этого определяется, какие должны быть сигналы на выходах элементов, подключенных к выходному ЛЭ. В свою очередь, сигналы на выходах этих элементов можно заменить соответствующими покрытиями, т.е. определить значения выходных сигналов для других ЛЭ и т.д. Этот процесс продолжается до тех пор, пока не получатся покрытия, состоящие только из входных переменных, называемых опорными. Совокупность таких покрытий и дает соответствующее покрытие схемы.

Пример анализа КС (рис 9. ) методом p - алгоритма представлен в табл. 5. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии для обеспечения заданного значения выходного сигнала. По-

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

На основании полученного единичного покрытия можно записать БФ, реализуемую схемой:

Таблица 5 Анализ схемы методом p – алгоритма.

а) Получение первого покрытия

б) Получение нулевого покрытия

В дальнейшем можно сравнить полученную БФ с той, по которой строилась схема и проверить правильность ее построения. При анализе схемы может оказаться, что некоторая переменная, получившая на одном из предыдущих шагов некоторые значения на данном шаге должна принять противоположное значение. Возникшее противоречие говорит о том, что данный путь является тупиковым и его необходимо исключить из дальнейшего рассмотрения. Если ни при одной комбинации входных переменных не обеспечивается значение 1(0) на выходе, то это означает, что схема реализует константу 0(1) соответственно.

1. 8 Анализ КС методом синхронного моделирования.

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

Рассмотрим метод синхронного моделирования на примере схемы ( рис.9 ).

На первом этапе схему разбиваем на уровни и записываем в порядке возрастания уровня уравнения, описывающие функционирование ЛЭ:

Проанализируем схему при подаче на вход набора X₁ =0, Х₂ =0, Х₃ =0, Х₄ =1, Х₅ =1. Для этого решаем записанные уравнения в порядке возрастания уравнения. Имеем:

;

;

;

.

Следовательно, при подаче на вход набора {00011}, на выходе будет Y=1. Аналогично можно промоделировать работу схемы при подаче на вход любого другого набора.

1.9 Анализ КС методом асинхронного моделирования.

Реальный ЛЭ переключается за какое-то конечное время, зависящее от технологии изготовления, условий эксплуатации, емкостей нагрузки и т.д. Прохождение сигнала последовательно через несколько ЛЭ будет приводить к накоплению времени задержки и возникновению сдвига во времени выходного сигнала по отношению ко входному. Наличие задержки и порождаемого ею временного сдвига сигналов может приводить к появлению на выходе отдельных ЛЭ и всей схемы в целом кратковременных сигналов, не предусмотренных БФ, реализуемой схемой. Как иллюстрацию, рассмотрим схему рис.11, а .

Рис. 11 а)

Рис. 11 . Статический риск сбоя.

а)- схема, б)- временные диаграммы.

t₁ -время задержки инвертора

t₂ -время задержки элемента 2И

Данная схема реализует функцию , т.е. константу 0 независимо от входного сигнала X. Однако в переходном процессе в результате задержки срабатывания ЛЭ возможна ситуация, когда на обоих входах элемента 2И будут логические единицы, что может привести к появлению на выходе схемы логической 1 (см. рис.11 б). Рассмотренный случай возможен при задержке срабатывания второго элемента больше, чем первого. Такое явление называется риском сбоя . Различают статистический и динамический риски сбоя.

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

При динамическом риске сбоя до и после переходного процесса состояния выходного сигнала противоположные, но в переходном процессе выходной сигнал несколько раз меняет свое значение. Динамический риск сбоя возможен в схеме (рис.12 а) при смене набора (Х₁ =0, Х₂ =1, Х₃ =1) на набор (Х₁ =1, Х₂ =0, Х₃ =0) и иллюстрируется диаграммами (рис.12 б).

В данном примере динамический риск сбоя на выходе КС сопровождается статическим на выходе элемента 1. Как видно из временных диаграмм риск сбоя имеет место при наличии определенного временного сдвига между сигналами, поступающими на вход ЛЭ. Нежелательные сигналы на выходе могут и отсутствовать при другом соотношении временных сигналов, однако принципиальная возможность их появления является фактором снижающим надежность работы схемы. Поэтому очень важно уметь обнаруживать и устранять такие явления.

Для анализа процесса переключения КС при смене входных наборов и обнаружения рисков сбоя используется метод асинхронного моделирования . При этом методе считается, что каждый элемент переключается с одинаковой задержкой. Анализ включает такие этапы:

1.Каждому элементу схемы присваивается уровень, причем уровень 1 имеют элементы, все входы которых являются независимыми входами схемы.

2.Записываются уравнения, описывающие каждый ЛЭ в порядке убывания уровня.

3.Для исходного входного набора А(X₁ , X₂ , … , X_n ) определяется значение сигналов на выходах всех ЛЭ схемы. Пусть данный набор А заменяется набором В(X₁ , X₂ , … , X_n ).

4.Помечаются те уравнения, в правой части которых хотя бы одна из переменных изменила свое значение.

5.Решаются помеченные уравнения в порядке их записи в схеме . После решения уравнение считается непомеченным.

6.Если после решения всех уравнений системы переменные, входящие в левые части уравнений, изменили свои значения, то вновь помечаются те уравнения, в правые части которых входят эти переменные. Затем осуществляется переход к п.5. В противном случае моделирование данного входного набора считается законченным. Выполнение п.5 называется тактом моделирования.

Анализ схемы (рис.13) методом асинхронного моделирования приведен ниже. Для данной схемы входной набор А(1011110) заменяется набором В(1101011).

Рис. 13. Комбинационная схема для метода асинхронного моделирования.

Уравнения, описывающие ЛЭ:

Табл. 6 Таблица моделирования схемы

Выходы Такты моделирования Прим.

0 1 2 3

e₆ 1 0 1 0 дин.

e₅ 0 1 0 0 стат.

e₄ 0 0 0 0

e₃ 1 0 0 0

e₂ 1 0 0 0

e₁ 0 1 0 1

Как следует из результатов моделирования, при смене набора А набором В на выходе элемента 4 имеет место статический риск сбоя, а на выходе схемы - динамический риск сбоя.

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

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ АБСТРА K ТНЫХ АВТО­МАТОВ .

Ознакомившись в курсах "Программирование" и "Машинная арифметика" с принципами работы ЭЦВМ, можно ука­зать на две основные особенности таких вычислительных машин: оперирование данными, представленными в цифровой форме и автоматическая работа по заранее составленной программе. Эти особенности показывают, что любая ЭЦВМ является цифровым автоматом (ЦА). Понятие ЦА служит обобщением для всех видов устройств обработки цифровой информации, имеющих программное управление.

Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воз­действием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт­ный автомат, определенный как 6-компонентный кортеж: S=(A,Z,W,d,l,а₁ ) у которого:

1. A={a₁ , a₂ , ... ,a_m } - множество состояний (внутренний алфавит)

2. Z={z₁ , z₂ , ... ,z_f } - множество входных сигналов (входной алфавит)

3. W={w₁ , w₂ , ..., w_g } - множество выходных сигналов (выходной алфавит)

4. d : A·Z®A - функция переходов, реализующая отображение D_d Í А·Z в А. Иными словами функция d некоторым парам состояние - входной сигнал (а_m , z_f ) ставит в соответствие состояния автомата а_s = d (a_m , z_f ), a_s Î A.

5. l : A·Z®W - функция выходов, реализующая отображение D_l Í А·Z на W. Функция l некоторым парам состояние - входной сигнал (а_m , z_f ) ставит в соответствие выходные сигналы автомата Wg=l(а_m , z_f ) , WgÎ W.

6. a_i Î A - начальное состояние автомата.

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

Абстрактный автомат (рис.14) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном со­стоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t) Î Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита W(t)=l(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=d[a(t), z(t)], a(t) Î A, w(t) Î W.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов вход­ного алфавита Z во множество слов выходного алфавита W. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1),... - выходное слово. Т.о. выходное слово = j(входное слово), где j - отображение, осуществляемое абстрактным автоматом.

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

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

На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), t = 0,1,2,...

Закон функционирования автомата Мура задается уравнениями:

a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), t = 0,1,2,...

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

Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так на­зываемым С- автоматом.

Под абстрактным С- автоматом будем понимать математическую модель дискретного устройства, определяемую восьми­компонентным вектором S=( A, Z, W, U, d, l₁ , l₂ , а₁ ), у которого:

1. A={a₁ , a₂ , ... ,a_m } - множество состояний;

2. Z={z₁ , z₂ , ... ,z_f } - входной алфавит;

3. W={w₁ , w₂ , ..., w_g } - выходной алфавит типа 1;

4. U={u₁ , u₂ ,...,u_h } - выходной алфавит типа 2;

5. d : A · Z ® A - функция переходов, реализующая отображение D_d Í А·Z в А;

6. l₁ : A · Z ® W - функция выходов, реализующая отображение D_{l 1} Í А·Z в W;

7. l₂ : A ® U - функция выходов, реализующая отображение D_{l 2} Í А в U;

8. а₁ Î А - начальное состояние автомата.

Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов l₁ и l₂ , каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:

а( t + 1) = d( a( t ), z( t )); w( t ) = l₁ ( a ( t ), z( t )); u( t ) = l₂ ( a( t )); t = 0, 1, 2, ...

Выходной сигнал U_h =l₂ ( a_m ) выдается все время, пока автомат находится в состоянии a_m . Выходной сигнал Wg=l₁ ( a_m , z_f ) выдается во время действия входного сигнала Z_f при нахождении автомата в состоянии a_m .

Рассмотренные выше абстрактные автоматы можно разделить на:

1) полностью определенные и частичные;

2) детерминированные и вероятностные;

3) синхронные и асинхронные;

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

Частичным называется абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функ­ции определены не для всех пар ( a_i , z_j ).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов : автомат, находя­щийся в некотором состоянии a_i , под действием любого входного сигнала z_j не может перейти более, чем в одно состоя­ние.

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

Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния . Состояние a_s автомата называется устойчивым, если для любого состояния a_i и входного сигнала z_j таких, что d( a_i , z_j ) = a_s имеет место d( a_s , z_j ) = a_s , т.е. состояние устойчиво, если попав в это состояние под действием некоторого сиг­нала zj, автомат выйдет из него только под действием другого сигнала z_k , отличного от z_j .

Автомат, у которого все состояния устойчивы - асинхронный .

Автомат называется синхронным , если он не является асинхронным.

Абстрактный автомат называется конечным , если конечны множества А = {a₁ , a₂ , ..., a_m }, Z = {z₁ , z₂ , ..., z_f }, W = {w₁ , w₂ , ..., w_g }. Автомат носит название инициального , если в нем выделено начальное состояние a₁ .

СПОСОБЫ ОПИСАНИЯ И ЗАДАНИЯ АВТОМАТОВ.

Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а₁ ). Множества А, Z, W описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций d и l ( следовательно и всего автомата в целом ) наибольшее распространение получили табличный и графиче­ский.

При табличном способе задания автомат Мили описывается с помощью двух таблиц. Одна из них (таблица переходов ) задает функцию d, т.е. a( t +1) = d( a( t ), z( t )) ( табл.7), вторая (таблица выходов ) - функцию l, т.е. W( t )=l( a( t ), z( t )) ( табл. 8 ).

Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z. На пересечении столбца a_m и строки z_f в табл.7 записывается состояние a_s , в которое должен перейти автомат из состояния a_m под действием входного сигнала Z_f , т.е. a_s = d(a_m , z_f ). На пересечении столбца a_m и строки z_f в табл.8 записывается выходной сигнал Wg, выдаваемый автоматом в состоянии a_m при поступ­лении на вход сигнала z_f , т.е. Wg = l( a_m , z_f ).

Для приведенных таблиц множества, образующие автомат A={a₁ , a₂ , a₃ ,a₄ }, Z={z₁ , z₂ }, W={w₁ , w₂ , w₃ , w₄ , w₅ }. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл.9), в которой каждый элемент a_s / w_g записанный на пересечении столбца a_m и строки z_f , определяется следующим образом:

a_s =d(a_m , z_f ); w_f =l(a_m , z_f ).

Автомат Мура задается одной отмеченной таблицей переходов (табл.10), в которой каждому столбцу приписаны не только состояние a_m , но еще и выходной сигнал Wg, соответствующий этому состоянию, где Wg=l(a_m ).

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

Для задания С - автоматов также используется табличный метод. В этом случае таблица переходов (табл.11) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим выходным сигналом u_i выходного алфавита типа 2 (табл.12)

При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a_m , задает переход в автомате из состояния a_m в состояние a_s . В начале этой дуги записывается входной сигнал Z_f ÎZ, вызывающий данный переход a_s =d(a_m ,z_f ). Для графа автомата Мили выходной сигнал w_g ÎW, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной a_m , отмеченной состоянием a_m , в котором он формируется. Если переход в автомате из состояния a_m в состояние a_s производится под действием нескольких входных сигналов, то дуге графа, направленной из a_m в a_s , приписываются все эти входные и соответствующие выходные сигналы. Граф С- автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Графы автоматов, заданных своими таблицами переходов и выходов
(табл. 7¸12) представлены на рисунках 15,16,17.

СВЯЗЬ МЕЖДУ МОДЕЛЯМИ МИЛИ И МУРА.

Рассмотрим некоторый автомат Мили, заданный таблицами переходов и выходов. Таблица переходов а) и выходов б) автомата Мили

Подадим на вход автомата, установленного в состояние а₁ , входное слово x=z₁ z₂ z₂ z₁ z₂ z₂ . Так как d(а₁ , z₁ ) = a₂ , l(a₁ , z₁ ) = W₂ , то под воздействием входного сигнала z₁ автомат перейдет в состояние а₂ и выдаст на переходе выходной сигнал W₂ . Затем, находясь в состоянии а₂ под воздействием сигнала Z₂ перейдет в состояние а₁ =d(а₂ , z₂ ) и выдаст сигнал W₁ =l(a₂ , z₂ ) и т.д. В табл. 13 приведена последовательность состояний, которые автомат проходит, воспринимая входное слово x, и выходные сигналы, вырабатываемые на этих переходах.

Назовем выходное слово w = l (a_1, x) реакцией автомата Мили в состоянии а₁ на входное слово x.

В нашем случае w = w₂ w₁ w₂ w₂ w₁ w₂

Как видно, из приведенного примера, в ответ на входное слово длины k автомат Мили выдаст последовательность состояний длины k +1 и выходное слово длины k.

В общем виде поведение автомата Мили, установленного в состояние a_m , можно описать следующим образом (табл. 14).

Аналогично можно описать поведение автомата Мура, находящегося в состоянии a₁ , при приходе входного слова

x = Z_i1 , Z_i2 , . . . , Z_ik ,учитывая, что W( t ) = l(a( t )):

Очевидно, что для автомата Мура выходной сигнал W_{i 1} = l(a_m ) в момент времени i₁ не зависит от входного сигнала Z_{i 1} и определяется только состоянием a_m . Следовательно, сигнал W_{i 1} никак не связан с входным словом x.

В связи с этим под реакцией автомата Мура, установленного в состояние a_m , на входное слово x = Z_{i 1} , Z_{i 2} , . . . , Z_ik будем понимать выходное слово той же длины w = l(a_m , x) = W_{i 2} W_{i 3} ...W_{ik +1} , сдвинутое по отношению к x на один такт.

Рассмотрим пример. Пусть задан автомат Мура:

Подадим на вход этого автомата ту же последовательность, что и для автомата Мили: x=z₁ z₂ z₂ z₁ z₂ z₂ . Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:

Сравнивая реакции автомата Мили (табл. 13) и автомата Мура (табл.15), отмечаем, что эти реакции на одно и то же слово x совпадают. Следовательно автоматы Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными. Строгое определение эквивалентности следующее:

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

Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура и наоборот.

Переход от автомата Мура к эквивалентному ему автомату Мили тривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходной сигнал Wg, записанный рядом с вершиной a_s исходного автомата Мура, перенести на все дуги, входящие в эту вершину. На рис. 18 приведен граф автомата Мили, эквивалентного автомату Мура (рис. 16)

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

Переход от автомата Мили к эквивалентному ему автомату Мура более сложен. Это связано с тем, что в автомате Мура в каждом состоянии вырабатывается только один выходной сигнал. Как и в предыдущем случае, переход наиболее наглядно делать при графическом способе задания автомата. В этом случае каждое состояние a_i исходного автомата Мили порождает столько состояний автомата Мура, сколько различных выходных сигналов вырабатывается в исходном автомате при попадании в состояние a_i . Рассмотрим переход от автомата Мили Sa к автомату Мура S_b на примере автомата (рис. 15).

Как следует из рис. 15 для автомата Sa при попадании в состояние а₁ вырабатываются выходные сигналы W₂ , W₄ , W₅ , при попадании в а₂ – W₁ , W₂ , a₃ – W₂ , a₄ – W₃ . Каждой паре состояние a_i - выходной сигнал Wj, который вырабатывается при попадании в это состояние, поставим в соответствие состояние b_k эквивалентного автомата Мура S_b с тем же выходным сигналом Wj : b₁ = (a₁ , W₂ ), b₂ = (a₁ , W₄ ), b₃ = (a₁ , W₅ ), b₄ = (a₂ , W₁ ), b₅ = (a₂ , W₂ ), b₆ = (a₃ , W₂ ), b₇ = (a₄ , W₃ ), т.е. каждое состояние a_i автомата Мили порождает некоторое множество A_i состояний эквивалентного автомата Мура: A₁ = { b₁ , b_­2 , b₃ }, A₂ = { b₄ , b₅ }, A₃ = { b₆ }, A₄ = { b₇ }. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа S_b поступаем следующим образом. Т.к. в автомате S_a есть переход из состояния а₁ в состояние а₂ под действием сигнала z₁ с выдачей W₁ , то из множества состояний A₁ = {b₁ , b₂ , b₃ }, порождаемых состоянием а₁ автомата S_a в автомате S_b должен быть переход в состояние (a₃ , W₂ ) = b₆ под действием сигнала Z₂ и т.д. Граф эквивалентного автомата Мура представлен на рис.19.

Если от автомата Мура S_b , эквивалентного автомату Мили Sa (рис. 19) вновь перейти к автомату Мили, то получим автомат Мили S₁ (рис. 20)

Вследствие транзитивности отношения эквивалентности два автомата Мили S₁ и Sa также будут эквивалентными, но у последнего будут на 3 состояния больше. Т.о., эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (т.е. с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов.

МИНИМИЗАЦИЯ ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ АВТОМАТОВ.

Рассмотрим метод минимизации полностью определенных автоматов, предложенный Ауфенкампом и Хоном.

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

Для пользования методом введем несколько определений.

Два состояния абстрактного автомата называются 1-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.

Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.

По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиения состояний автомата на ( i +1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на ¥ - классы эквивалентности.

Разбиение множества внутренних состояний автомата на ¥ - классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

Все вышеизложенное непосредственно применимо к минимизации автомата Мили. При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому классу относятся одинаково отмеченные состояния автомата Мура.

Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному для автоматов Мили.

Рассмотрим пример минимизации автомата Мили, заданного таблицами переходов и выходов :

Из таблицы выходов получаем разбиение на 1-классы эквивалентности p₁ , объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами:

p₁ = {B₁ , B₂ }; B₂ = {a₁ , a₂ , a₅ , a₆ }; B₂ = {a₃ , a₄ }

Для получения 2-эквивалентных состояний строим таблицу 1-разбиения (табл.17), заменяя в таблице переходов состояния a₁ соответствующими классами эквивалентности B1 или B2.

Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности C_i и разбиение p₂ = {C₁ , C₂ , C₃ }, где С₁ = {a₁ , a₁ }, C₂ = {a₅ , a₆ }, C₃ = {a₃ , a₄ }. Сравнивая p₂ и p₁ , отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 18), опять заменяя в таблице переходов состояния a_i соответствующими классами эквивалентности C_i .

Из полученной таблицы 2-разбиения получаем 3-классы эквивалентности D_i и разбиение p₃ ={ D₁ , D₂ , D₃ }, где D₁ = {a₁ , a₂ }, D₂ = {a₅ , a₆ }, D₃ = {a₃ , a₄ }.

Сравнивая p₃ и p₂ , замечаем, что D₁ = C₁ , D₂ = C₂ , D₃ = C₃ , p₃ = p₃ . Следовательно получили разбиение на ¥- эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса D_i по одному состоянию и получаем множество состояний A' минимального автомата. Пусть, например, A'={a₁ , a₄ , a₅ }. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 16) вычеркиваем столбцы, соответствующие "лишним состояниям" a₂ , a₃ , a₆ . В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 19).

Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.

Структурный синтез ЦА.

Задачи синтеза ЦА.

Канонический метод структурного синтеза ЦА.

Элементарные цифровые автоматы с памятью

(триггерные устройства) и их свойства.

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

В отличие от абстрактного автомата, имеющего один вход и один выход, на которые поступают сигналы во входном и выходят в выходном W={W₁ ,..,W_G } алфавитах, структурный автомат имеет L входных каналов х₁ ,х₂ ,..,х_L и N выходных y ₁ , y ₂ ,…, y_N на каждом из которых присутствует сигнал структурного алфавита.

Обычно в качестве структурного используется двоичный алфавит.

В этом случае каждому входному сигналу Z_F абстрактного автомата соответствует некоторый двоичный вектор (l_{f 1} ,l_{f 2} ,..,l_{f L} ) , где l_{f L} Î{0,1}.

Очевидно, что для представления (кодирования) входных сигналов Z₁ ,..,Z_F абстрактного автомата различными двоичными векторами должно быть выполнено условие

L ] log₂ F [ ,

аналогично

N ] log₂ G [

Например , Z={Z₁ ,Z₂ ,Z₃ ,Z₄ } W={W₁ ,W₂ ,W₃ } .

Тогда L log₂ 4=2 N log₂ 3=2

Закодировать входные и выходные сигналы можно ,например, так:

Z₁ = 00 W₁ = 00

Z₂ = 01 W₂ = 01

Z₃ = 10 W₃ = 11

Z₄ = 11

Задача синтеза структуры автомата.

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

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

Теоретическим обоснованием канонического метода структурного синтеза автоматов служит теорема о структурной полноте :

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

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

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

Канонический метод структурного синтеза предполагает представление структурной схемы автомата в виде двух частей: памяти и комбинационной схемы.

Память состоит из элементарных автоматов Мура П₁ ,....,П_Z ,....,П_R . После выбора элементов памяти каждое состояние синтезируемого автомата А кодируется набором их состояний. Если все автоматы П₁ ...,П_R одинаковы, что в общем случае необязательно, то их число

где M – число состояний синтезируемого автомата А , а b – число состояний элементарного автомата памяти. Обычно для элементарного автомата b =2, тогда .

Например, переход автомата А , имеющего 5 элементов памяти, алфавит состояний которых – двоичный, из одного состояния (A _m )=01011 в другое (A ₃ )= 11000, заключается в изменении состояний соответствующих автоматов памяти: первый элемент памяти переходит из 0 в 1, второй – из 1 в 1, третий из 0 в 0, четвёртый – из 1 в 0, пятый - из 1 в 0.

Переходы автоматов памяти, соответствующие переходам в автомате А , происходят под действием сигналов возбуждения памяти, поступающих с выхода комбинационной схемы на вход памяти автомата. Так на рисунке X =(X ₁ ,X ₂ ,..,X _L ) и Y =(Y ₁ ,Y ₂ ,...,Y _N ) – векторные структурные входной и выходной сигналы автомата, U =(U ₁ ,U ₂ ,...,U _T ) – векторная функция возбуждения памяти и Q =(Q ₁ ,...,Q _T ) – вектор выходного сигнала обратной связи от элементов памяти автомата.

Рассмотрим отдельно элемент памяти П_z , таблица переходов которого дана в таблице. Множество выходных сигналов элементов памяти совпадает с множеством внутренних состояний.

Полнота переходов очевидна из таблицы (в каждом столбце все состояния встречаются). При рассмотрении автомата на абстрактном уровне его можно представить в виде рис.22 а .

При переходе от абстрактного автомата к структурному, входные и выходные сигналы должны быть закодированы наборами сигналов структурного алфавита (входного или выходного соответственно). При двоичном структурном алфавите автомат П_z будет иметь два входных и два выходных канала.

Итак, сами компоненты U _z и Q _z при Z = 1,...,R векторов сигналов возбуждения памяти U и сигналов обратной связи от памяти Q также могут быть представлены в виде векторов:

U _z = (U _Z1 ,U _Z2 ,...,U _{Z K} ) и Q _Z = (Q _{Z 1} ,Q _{Z 2} ,...,Q _{Z R} ).

Если не оговорено особо, то используется двоичный структурный алфавит как для входных и выходных каналов синтезируемого автомата, так и для входных и выходных каналов автоматов памяти. Алфавит состояний автоматов памяти также обычно двоичный.

При построении функций возбуждения памяти автомата используют функцию входов элемента памяти m(b _i ,b _j ), ставящую в соответствие каждой паре состояний (b _i ,b _j ) сигнал, который должен быть подан на вход этого автомата для перевода его из состояния b _i в состояние b _j . Функцию входов удобно задавать в виде таблицы. Для элемента памяти (функция переходов которого приведена ранее) функция входов имеет вид:

Если входные сигналы элемента памяти q ₁ ,...,q _p закодированы наборами (U _{Z 1} ,...,U _{Z K} ) сигналов на его входных каналах, то элементами таблицы, задающей функцию входов вместо q _i будут соответствующие наборы. Так, если q ₁ = 00, q ₂ = 01, q ₃ = 10, то соответствующая f входов будет иметь вид рис.23a.

Элементарные цифровые автоматы – элементы памяти.

В качестве элементов памяти структурного автомата обычно используются триггеры.

Триггер – это устройство, имеющее два устойчивых состояния, в которые он переходит под действием определённых входных сигналов.

Обычно в триггерах выделяют два вида входных сигналов (и соответственно входов): информационные и синхросигналы.

Информационные сигналы определяют новое состояние триггера и присутствуют в любых триггерах. По типу информационных сигналов осуществляется классификация триггеров: D, T, RS, JK, RST, DV и т.д.

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

На синхровход триггера поступают тактирующие импульсы задающего генератора, синхронизирующего работу ЦА. Период следования импульсов соответствует одному такту автоматного времени ЦА.

Рассмотрим основные типы триггеров, используемые для синтеза ЦА: D, T, RS, JK .

D -триггер – элемент задержки – имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт.

Условное обозначение и таблица переходов D -триггера представлена на рис. .

Из приведенной таблицы переходов для данного триггера Q ^t+1 = f (Q ^t ,D ^t ) можно получить таблицу функций его входов D ^t = j(Q ^t , Q ^t+1 ).

Как видно из таблицы, состояние, в которое переходит триггер (средний столбец), совпадает с поступившим на его вход сигналом D (t ) (правый столбец). В связи с этим таблица функций возбуждения памяти синтезируемого автомата с использованием D -триггеров будет полностью совпадать с кодированной таблицей переходов этого автомата. Промышленность выпускает D -триггера в интегральном исполнении. Например,

K155TM2 (рис. 25).Таких триггеров два в одном корпусе. Вход С –вход синхронизации, Q ,` Q – выходы, Q – прямой, – инверсный. R , S – входы установки в 0 и 1 соответственно. При подаче на вход R и S логического нуля триггер устанавливается в соответствующие состояния независимо от сигнала на входах D и C .

T -триггер – триггер со счетным входом – имеет один информационный вход Т и один выход Q и осуществляет суммирование по модулю два значений сигнала T и состояния Q в заданный момент времени.

Условное обозначение и таблица переходов T- триггера представлена на рис 26.

Таблица функций входов триггера T ^t = f (Q ^t , Q ^t+1 ) представлена в таблице.

На основании этой таблицы можно получать функцию возбуждения элементов памяти при синтезе автомата на базе T -триггера. Например, если автомат перешел из состояния a _i = 010 в состояние a _j = 110, то для обеспечения этого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 T ₁ = 1,

для второго триггера при переходе из 1 в 1 T ₂ = 0,

для третьего триггера при переходе из 0 в 0 T ₃ =0 и т.д.

В чистом виде промышленность не выпускает T -триггера.

RS -триггер – триггер с раздельными входами.

Данный триггер имеет два входных канала R и S и один выходной Q . Вход S (set) называется входом установки в единицу, вход R (reset) – входом установки в нуль. Условное обозначение и таблица переходов RS -триггера представлена на рис. 27.

В таблице переходов при подаче комбинации S = R = 1 состояние перехода Q ^t+1 не определено и эта комбинация сигналов является запрещенной для RS -триггера.

Таблицу переходов можно более компактно изобразить в виде (см. табл. 21б) Анализируя табл.21 б,в отмечаем что, например, переход триггера из 0 в 0требует подачи комбинации R =0, S =0 или R =1,S =0, т.е. можно сказать что этот переход будет при R =X (безразличное состояние) , S =0.

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

На основании таблицы можно получить функцию возбуждения памяти автомата при синтезе на базе RS -триггеров. Например, если автомат переходит из состояния a_i = 010 в состояние a_j =110, то для обеспечения такого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 R ₁ =0, S ₁ = 1;

для второго триггера при переходе из 1 в 1 R ₂ =0, S ₂ = X;

для третьего триггера при переходе из 0 в 0 R ₃ =X, S ₃ = 0.

Аналогично для любого другого перехода автомата.

В чистом виде синхронный RS - триггер, используемый для синтеза ЦА, промышленностью не выпускается.

JK- триггер – имеет два информационных входа J и K и один выход Q . Вход J – вход установки в 1, вход K – вход установки в 0, т.е. эти входы аналогичны соответствующим входам RS -триггера: J – соответствует S , K – соответствует R . Однако, в отличие от RS -триггера, входная комбинация J = 1, K = 1 не является запрещённой. Условное обозначение и таблица переходов JK -триггера представлены на рис.28. и в табл. 22.

Как следует из таблиц переходов, для комбинаций входных сигналов JK = 00¸10 триггер ведет себя как RS -триггер, а при комбинации JK = 11 – как T -триггер.

Анализируя таблицу переходов ( табл. 22 а), отмечаем, что переход триггера, например, из 0 в 1 требует подачи входных сигналов J =1, K =0 или J =1, K =1, т.е. J =1, K =Х (безразличное значение). Аналогично рассуждая по отношению к другим переходам, получим следующую таблицу функций входов JK -триггера.

На основании последней таблицы можно получить функцию возбуждения элементов памяти при синтезе автомата на JK -триггерах. Например, при переходе автомата из состояния a_i =010 в состояние a_j =110, функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 J 1 = 1, K 1 = X;

для второго триггера при переходе из 1 в 1 J 2 = X, K 2 = 0;

для третьего триггера при переходе из 0 в 0 J 3 = 0, K 3 = X.

Пример канонического метода структурного синтеза автомата.

Выполним структурный синтез частичного автомата А , заданного своими таблицами переходов и выходов (табл. 23 и 24.).

Синтез будем выполнять в следующем порядке:

1. Выберем в качестве элементов памяти D -триггер, функция входов которого представлена в таблице стр. 33.

2. Закодируем входные, выходные сигналы и внутренние состояния автомата. Количество входных абстрактных сигналов F = 3, следовательно количество входных структурных сигналов L = ]log ₂ F [ = ]log ₂ 3[ = 2, т.е. х ₁ , х ₂ .

Количество выходных абстрактных сигналов G = 4, следовательно количество выходных структурных сигналов N =]log₂ G [ = ]log₂ 4[ = 2, т.е. у ₁ , у ₂ . Количество внутренних состояний абстрактного автомата M = 4, следовательно количество двоичных элементов памяти (триггеров) R = ] log ₂ M [ = ]log ₂ 4[ = 2.

Следовательно, структура ЦА с учетом того, что исходный автомат является автоматом Мили, в качестве элементов памяти используется D -триггер, может быть представлена в виде(рис. 29):

Кодирование входных, выходных сигналов и внутренних состояний представлена в таблицах:

Кодирование, в общем случае, осуществляется произвольно. Поэтому, например, каждому из сигналов Z_i можно поставить в соответствие любую двухразрядную комбинацию х ₁ , х ₂ . Необходимо только, чтобы разные выходные сигналы Z_i кодировались разными комбинациями х ₁ , х ₂ . Аналогично для W_i и a _i .

3. Получим кодированные таблицы переходов и выходов структурного автомата. Для этого в таблицах переходов и выходов исходного абстрактного автомата вместо Z_i , W_i , a_i cтавим соответствующие коды. Получим таблицы:

В кодированной таблице переходов заданы функции

В кодированной таблице выходов заданны функции:

4. При каноническом методе синтез сводится к получению функций:

и последующем построении комбинационных схем, реализующих данную систему булевых функций.

Функции у ₁ и у ₂ могут быть непосредственно получены из таблицы выходов, например, в виде :

Однако выражения для у ₁ и у ₂ можно существенно упростить в результате минимизации, например, с помощью карт Карно:

В результате минимизации имеем:

Для получения выражений для D ₁ и D ₂ необходимо получить таблицы функций возбуждения. Для чего в общем случае необходимо воспользоваться таблицей переходов и функциями входов элементов памяти. Зная код исходного состояния автомата и код

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

В результате минимизации получаем:

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

Функциональная схема автомата представлена на странице 41:

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

Особенности синтеза автоматов на базе T , RS , JK триггеров.

Необходимо отметить, что синтез на базе указанных типов триггеров осуществляется аналогично выполненному синтезу на базе D -триггеров. В частности, п. 1¸3 (см. предыдущий параграф) абсолютно аналогичны. Кроме того, как следует из п.4 (см. предыдущий параграф) выходные сигналы не зависят от типа триггеров, поэтому выражение для y_i будут одинаковыми для любого типа триггеров. Однако функции возбуждения будут различны для разных типов триггеров и получаются на основании таблицы переходов исходного автомата и функции входов выбранного триггера. Без особых пояснений ниже приведены таблицы функций входов, функций возбуждений и карты Карно для минимизации функций возбуждения при использовании для синтеза автомата предыдущего параграфа T -, RS -, JK -триггеров.

T -триггер .

RS - триггер .