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

Текст из файла (страница 12)

способами, где . Если n=2^k, то число вариантов кодирования в точности равно n! Выбирается такой вариант кодирования, который обеспечивал бы минимальные аппаратные затраты. Эффективных алгоритмов выбора оптимальных вариантов кодирования не существует, и задача решается методом перебора.

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

Н апример, пусть для ЭА Q₁,Q₂,Q₃ имеем переход из a_k=<1,0,0> в a_m=<1,1,1>.

При переходе может возникнуть состояние <1,1,0>, если Q₂ быстрее изменяет своё состояние, чем Q₃ (гонки выигрывает Q₂) или <1,0,1>, если Q₃ быстрее изменяет своё состояние, чем Q₂ (гонки выигрывает Q₃). Возможны два случая:

В
случае «а» при воздействии входного сигнала x_i достигается верное состояние a_m, в случае «б» вместо состояния a_m переходим в другое состояние a_l. В первом, случае автомат функционирует правильно, и гонки являются некритическими, во втором неправильно - гонки являются критическими.

Для борьбы с состязаниями используют различные методы:

1) Противогоночное кодирование состояний автомата. Оно приводит к увеличению числа состояний автомата. Частным случаем такого кодирования является соседнее кодирование, при котором на каждом переходе изменяется состояние только одного ЭА: 101111110100…

2) Тактирование входных сигналов С_i C_i. В этом случае предъявляются жёсткие условия к длительности тактирующего сигнала , которая должна быть не больше времени задержки в цепи обратной связи.

3) Использование двойной памяти на MS – триггерах и им подобных.

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

Пример 3.2.

Осуществим кодирование символов алфавитов абстрактных автоматов S₁ и S₂ из раздела 3.2.2. Они заданы на входном x={x₁,x₂,x₃,x₄} и выходном y={y₁,y₂,y₃} алфавитах. Кроме того автомат Мура S₁ определён на алфавите состояний A₁={a₁,a₂,a₃,a₄}, а автомат Мили S₂ на алфавите A₂={a₁,a₂,a₃}.

Определим разрядность кодов символов:

1. алфавита состояний для S₁: n_Q=]log₂n_a[=log₂4=2 (автомат Мура).

Возможно n_a!=4!=24 способов кодирования для S₂: n_Q=]log₂n_a[=]log₂3[=2 (автомат Мили).

Возможно =4*3*2=24 способов кодирования.

1. входного алфавита

n_C=]log₂n_X[=log₂4=2

Возможно n_X!=4!=24 вариантов кодирования.

1. Выходного алфавита

n_Z=]log2n_Y[=]log₂3[=2

Возможно =4*3*2=24 вариантов кодирования.

Д
ля автомата S₂ таблицу кодирования символов алфавита состояний A₂ включает только первые три строки таблицы на рис. 3.22. Структурные автоматы имеют n_C=2 входов, n_Z=2 выходов и реализуются на n_Q=2 элементарных автоматах.

3.3.3. Получение кодированной таблицы переходов и выходов.

Исходными данными для построения кодированной таблицы переходов и выходов являются:

1) Таблицы переходов и выходов абстрактного автомата.

2) Таблицы кодирования символов алфавита абстрактного автомата.

Таблица кодирования получается путём подстановки двоичных кодов символов в таблицу переходов и выходов абстрактного автомата.

Пример 3.3.:

д
ля описанных выше автоматов S₁ и S₂ кодированные таблицы переходов и выходов. Они получаются путём кодирования таблиц на рис. 3.8 и 3.9. с использованием таблиц на рис. 3.20.,3.21. и 3.22.

Таблицы задают переходы элементарных автоматов. По кодированной таблице переходов находят функции внешних переходов элементарных автоматов, а по кодированной таблице выходов - функции выходов.

3.3.4. Определение функций внешних переходов.

Функции внешних переходов определяется в следующей последовательности.

1) Переставить строки столбцы таблицы переходов-выходов таким образом, чтобы значение входного сигнала и состояний элементарных автоматов в момент t образовывали циклический код.

2 ) Размножаем (распараллеливаем) таблицу переходов по числу элементарных автоматов и таблицу переходов для каждого автомата представляется в виде диаграммы Карно.

1. По диаграмме Карно определяем функции внешних переходов.

Ниже определяются функции внешних переходов для автоматов S₁ и S₂. Преобразуем кодированные таблицы переходов и выходов на рис. 3.23. и 3.24. автоматов S₁ и S₂ переставив местами два последних столбца.

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

3.3.5 Элементарные автоматы и их свойства.

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

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

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

а) внутреннее состояние триггера обозначается буквой Q; при Q = 1 мы будем говорить о «единичном состоянии триггера», при Q = 0 – о «нулевом состоянии триггера»;

б) выходной сигнал триггера повторяет его внутреннее состояние и поэтому обозначается той же

буквой Q;

в) триггер имеет парафазный выход, формирующий сигналы Q и ;

г) триггер является синхронным элементарным автоматом; синхроимпульсы поступают на вход, обозначаемый буквой С;

д) сигнальные входы триггера принято делить на установочные и рабочие. Установочные сигналы подаются помимо комбинационной схемы формирования функций возбуждения К С Q, и служат для установки триггера в исходное состоя­ние (нулевое или единичное). Принято установочные сигналы обозначать через R_d (установка в «О») и S_d (установка в «1»).

Рабочие сигналы формируются на KCQ и изменяют состоя­ние триггера в процессе формирования выходного сигнала ав­томата; они обозначаются буквами D, T, R, S, J, K; Рабочие сигналы, как правило, тактируются. Входы могут быть статическими и динамическими. В случае статических входов состояний триггера изменение состояния триггера осуществляется по уровню сигнала. Установочные входы являются статическими. В случае динамических входов состояние изменяется по изменению сигнала (по фронту или срезу).

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

е) классификацию триггеров осуществляют во числу рабо­чих сигналов.

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

Рассмотрение триггеров мы начнем с их простейших мо­дификаций - триггеров с одним входом. Таких триггеров два: D - триггер и Т-триггер.

D - триггер (от английского delay — задержка) форми­рует выходной сигнал, логически совпадающий с входным сиг­налом, но задержанный относительно последнего на один период синхроимпульсов. На рис. 1 представлено графическое изображение триггера (а) и отображена его работа в виде таблицы переходов (б), графа (в) и матрицы переходов (г). При построении учитывалось свойство D-триггера: последующее состояние триггера Q(t+1) всегда совпадает со значе­нием его входного сигнала D (t). Для определения аналити­ческого выражения функции перехода можно воспользоваться таблицей перехода, представив в виде диаграммы Карно.

Q (t+1) = D(t)

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

Микросхемы D – триггеров входят в состав всех существующих серий интегральных цифровых схем. На рис. 3.29. изображён один из двух триггеров микросхемы К155ТМ2:

Рис. 3.29.

Другим одновходовым триггером является Т-триггер (от английского trigger - пусковое устройство, триггер), в Т-триггере входной сигнал, равный единице, изменяет его предыдущее состояние на противоположное, а нулевое значение входного сигнала сохраняет его предыдущее состояние. Описание

Т-триггера представлено на рис. 3.31, функция перехода определилась по таблице переходов как

Отдельно микросхем счётных триггеров не существует, но их можно реализовать на других триггерах. На рис. 3.32. приведены схемы асинхронного и синхронного счётного устройства на D- триггерах: а- асинхронный T-триггер , б- синхронный Т- триггер.

Характеристики

Список файлов лекций