Модуль 5. Структурные автоматы синхронного и асинхронного типов 1/43Теория автоматов. Модуль 5 Классический метод синтеза структурного (цифрового) автомата синхронного типа. Классический метод синтеза Асинхронные автоматы. Гонки в автоматах и способы борьбы с ними. Асинхронные автоматы Проблематика кодирования выходных сигналов и состояний синхронных автоматов. Проблематика кодирования Пример синтеза распределителя импульсов как автомата Мура. Пример синтеза Регистры и их классификация.Регистры Регистры памяти.Регистры памяти Синтез универсального регистра на D-триггерах динамического типа.Синтез универсального регистра Счётчики и их классификация.Счётчики Синхронные счётчики. Синтез реверсивного счётчика с объединённым входом.Синхронные счётчики

Классический метод синтеза структурного (цифрового) автомата синхронного типа 2/43Теория автоматов. Модуль 5 Метод рассмотрим на примере синтеза не полностью определённого автомата Мили. Автомат не требует минимизации состояний, т. к. в нём отсутствуют совместимые (1-эквивалентные) состояния. a1a1 a2a2 a3a3 z1z1 a 3 /w 2 a 1 /w 1 z2z2 a 3 /w 3 a 2 /w 2 z3z3 a 2 /w 4 a 2 /w 1 1). Произведём кодирование символов первичных алфавитов и состояний абстрактного автомата. Синим цветом выделено начальное состояние автомата x 1 x 2 \Q 1 Q /0101/ /1000/ /11 00/00 Zx1x1 x2x2 z1z1 00 z2z2 01 z3z3 10 Wy1y1 y2y2 w1w1 00 w2w2 01 w3w3 10 w4w4 11 AQ1Q1 Q2Q2 a1a1 01 a2a2 00 a3a3 10 2). Составляем кодированную таблицу переходов и выходов. 3). Выбираем тип триггера, выписываем триггерный словарь. Пусть это будет Т- триггер. Q t Q t+1 T

Продолжение синтеза автомата (стратегия минимальной стоимости) 3/43Теория автоматов. Модуль 5 4. Структурная модель автомата. 5. Преобразование кодированной таблицы переходов и выходов в таблицу истинности для выходных сигналов и сигналов возбуждения триггеров. Время tt+1t x1x2x1x2 Q1Q2Q1Q2 y1y2y1y2 Q1Q2Q1Q2 T1T2T1T Синтез комбинационной части (КС 1 и КС 2 ) автомата произведём с использованием стратегии минимальной стоимости, когда на неиспользуемых наборах x 1 x 2 и Q 1 Q 2 зададимся такими значениями для y i и T i, которые обеспечивали бы наилучшие условия минимизации. Неиспользуемые наборы на картах Карно отмечены символом «х», а неопределённые значения автомата в таблице переходов и выходов символом «--». X={x 1, x 2 } KC 1 KC 2 Q1Q1 Q2Q2 x1x1 x2x2 x1x1 x2x2 T1T1 T2T2.... y1y1 y2y2 Clk Q1Q1 Q2Q2 Q1Q1 Q2Q2 & ( ) 01 == 21 1 QQ aK

Синтез автомата (окончание - стратегия минимальной стоимости, начало - стратегия минимального риска) 4/43Теория автоматов. Модуль 5 0x1--10 xxxx11 0x x y 1 x1x2x1x2 Q1Q2Q1Q2 0x1--10 xxxx11 1x x y 2 x1x2x1x2 Q1Q2Q1Q2 1x0--10 xxxx11 1x x T 1 x1x2x1x2 Q1Q2Q1Q2 0x1--10 xxxx11 0x x T 2 x1x2x1x2 Q1Q2Q1Q2 7. После приведения полученных уравнений к заданному логическому базису приступают к построению КС 1 и КС 2 автомата. Возврат к П Синтез комбинационной части (КС1 и КС2) автомата с использованием стратегии минимального риска. Недостаток стратегии минимальной стоимости – поведение автомата может оказаться непредсказуемым, если в силу каких-либо причин (сбоя) автомат попадёт в неиспользуемое состояние. При стратегии минимального риска таблица истинности составляется таким образом, чтобы при любом входном воздействии x 1 x 2 автомат из неиспользуемого состояния (неопределённого) попадал в начальное состояние.

Синтез автомата (окончание - стратегия минимального риска) 5/43Теория автоматов. Модуль 5 Время tt+1t x1x2x1x2 Q1Q2Q1Q2 y1y2y1y2 Q1Q2Q1Q2 T1T2T1T X X X x x0xx T 2 x1x2x1x2 Q1Q2Q1Q x1xx T 1 x1x2x1x2 Q1Q2Q1Q2 - усложнилось - не изменилось Добавленная часть таблицы. Синим цветом выделено начальное состояние автомата

Синтез структурного автомата на основе кодированного графа автомата (подвид классического метода) 6/43Теория автоматов. Модуль 5 Полученные выражения в дальнейшем подвергаются минимизации. Вывод. Построение комбинационной части автомата по таблице истинности (классический метод) для функций выходов и возбуждения является более предпочтительным. Из графа можно получить ДНФ функций возбуждения и функций выходов x 1 x 2 \Q 1 Q /0101/ /1000/ /11 00/00 После того, как была получена кодированная таблица переходов и выходов, а также выбран тип триггера (этапы 2 и 3 классического синтеза структурного автомата) можно приступить к построению кодированного графа автомата. На дугах графа указываются только те выходные сигналы y i и сигналы возбуждения T j, которые на данном переходе имеют «1» -значения.

Асинхронные автоматы. Гонки в автоматах и способы борьбы с ними 7/43Теория автоматов. Модуль 5 1. Асинхронные автоматы. Как уже отмечалось ранее, цифровые автоматы могут быть синхронными и асинхронными. В асинхронных автоматах импульсы синхронизации отсутствуют, а состояния памяти автомата изменяется под воздействием внешних входных сигналов из семейства X={x 1, …, x k ). При этом память автомата может быть выполнена только на асинхронных триггерах, т.е. на триггерах RS – типа. Как следует из структурной схемы автомата, генерация сигналов возбуждения триггеров памяти осуществляется комбинационной схемой КС 1. Отметим две основные особенности процесса формирования сигналов возбуждения КС 1 : 1) каждая комбинационная цепь, формирующая сигналы возбуждения (RS) к – триггера характеризуется своим временем задержки, что порождает разновременное срабатывания триггеров. 2) поскольку комбинационная цепь, как правило, включает несколько ветвей, характеризующихся различным временем задержки прохождения сигнала от входа к выходу, то в процессе формирования истинного значения выходного сигнала, возможно появление ложных значений. Указанные ложные значения называются рисками. Риски могут привести к ложному срабатыванию триггера. Как первый, так и второй случаи, могут привести к сбою в алгоритме работы автомата.

2. Риски сбоя в комбинационных схемах 8/43Теория автоматов. Модуль 5 Риски сбоя в комбинационных схемах подразделяются на статические и динамические. Рассмотрим пример статического риска, когда окончательное значение выхода КС должно остаться неизменным (изменение сигнала не предусмотрено логикой функционирования схемы) при изменении входных сигналов & & Момент смены кода Ложный сигнал Момент фиксации Данный рисунок демонстрирует статический риск сбоя в «1». Динамический риск возникает, когда логика работы схемы предусматривает на выходе изменение состояния, однако вместо однократного перехода выходной величины происходят её многократные изменения. Здесь, T = t 1 -t 0 ->максимально возможная задержка в распространении сигнала

3. Гонки в асинхронных автоматах. 9/43Теория автоматов. Модуль 5 Итак, поскольку сигналы возбуждения φ r формируются различными участками КС автомата, то они поступают на входы триггеров с некоторым разбросом во времени. Переход автомата из одного состояния в другое может сопровождаться переключением нескольких триггеров, при этом возникают некоторые промежуточные состояния. Тот из них, который выиграл гонку (состязание), может через цепь обратной связи изменить сигналы возбуждения на входах некоторых триггеров до того как они переключаться. Это приведёт к сбою в работе автомата. Рассмотрим такой пример, когда автомат реализует переход a m a s Другая ветвь графа при этом же сигнале. Критический случай. Сбой. Некритический случай в гонках. T 2 выиграл гонку T 1 выиграл гонку Вновь выработанные сигналы возбуждения Сбой В графе автомата имеется переход a k a j при том же входном сигнале z f В примере используется асинхронный RS- триггер. При этом: k(a m )=(Q 1 Q 2 Q 3 Q 4 )=0101, k(a s )=(Q 1 Q 2 Q 3 Q 4 )=1001,

Способы борьбы с гонками 10/43Теория автоматов. Модуль 5 Различают аппаратные способы и способы, использующие противогоночное кодирование. Аппаратные способы приводят к необходимости использования импульсов синхронизации для регламентации процесса восприятия сигналов возбуждения триггерами, или в конечном счёте, к преобразованию асинхронного автомата в синхронный. Противогоночное кодирование имеет цель использования в асинхронных автоматах таких кодовых комбинаций для реальных состояний, которые бы не совпадали с промежуточными кодовыми комбинациями, возникающими в процессе гонок.

Соседнее кодирование 11/43Теория автоматов. Модуль 5 Одной из разновидностей противогоночного кодирования является соседнее кодирование. При соседнем кодировании любые два смежных состояния в графе автомата кодируются наборами Q 1,..., Q R, отличающимися состояниями лишь одного элемента (такие кодовые комбинации характеризуются минимальным кодовым расстоянием d=1), что исключает гонки, так как отсутствуют состязания между триггерами. Данный тип кодирования используется и в синхронных автоматах. На рисунке показан фрагмент графа, включающий два вложенных друг в друга цикла с чётным числом вершин. Соседнее кодирование состояний автомата легко реализуется наложением графа на карту Карно, соответствующей размерности Из графа автомата следует: Данные уравнения можно модифицировать, следуя асинхронному принципу функционирования автомата. Состояние автомата изменяется с изменением входных сигналов, но это изменение не должно влечь за собой изменение ранее выработанных сигналов возбуждения. А это возможно только тогда, когда сигналы возбуждения не зависят от состояния переключаемого триггера.

Соседнее кодирование (продолжение) 12/43Теория автоматов. Модуль 5 Действительно: Соседнее кодирование невозможно, если граф автомата содержит циклы с нечётным числом вершин. В этом случае иногда вводят фиктивные состояния, чтобы исключить циклы с нечётным числом вершин. Однако отмеченное условие не является достаточным и может быть сформулировано в терминах теории графов при рассмотрении отображения графа автомата в n-мерном кубе. На рисунке, в качестве примера, приведен граф с чётным числом вершин в циклах, для которого не удаётся реализовать соседнее кодирование Этим материалом заканчивается рассмотрение асинхронных автоматов в данном учебном курсе. Сигнал возбуждения третьего триггера S 3 не зависит от этого триггера

Проблематика кодирования выходных сигналов и состояний автомата 13/43Теория автоматов. Модуль 5 Каждому состоянию a j (т.е. вершине графа автомата) должна соответствовать одна определенная комбинация состояний триггеров Q 1,..., Q R. Различают два подхода к кодированию состояний автомата: случайное и экономичное. Экономичное кодирование, как правило, приводит к уменьшению сложности комбинационной части, которая формирует выходные сигналы управления и сигналы возбуждения элементов памяти автомата. Эмпирически установлено, что комбинационная схема проще тогда, когда каждое изменение состояния автомата вызывается действием как можно меньшего числа сигналов возбуждения триггеров. В наилучшей степени, этому критерию отвечает рассмотренное выше соседнее кодирование. Однако оно может быть реализовано только для отдельных фрагментов графа. Существует много способов экономичного кодирования, однако в большинстве случаев они весьма трудоемки в практическом использовании и требуют специальных знаний из области теории графов и автоматов. Из простых способов, относящихся к классу экономичного кодирования состояний автомата, отметим следующие три: кодирование с ослабленной зависимостью от входных сигналов; приоритетное кодирование логически смежных состояний; способ кодирования состояний автомата, минимизирующий суммарное число переключений элементов памяти на всех переходах автомата ( способ Д.З. Мороза). Способ соседнего кодирования используется как составная часть указанных выше способов.

Пример графа, для которого рассматриваются вышеуказанные способы кодирования состояний автомата 14/43Теория автоматов. Модуль 5 В лекционном материале для сравнительного анализа способов кодирования взят один и тот же граф автомата с 5-ю вершинами. Граф не содержит петель, поскольку они не влияют на характер (качество) кодирования. Кроме того на графе не указаны выходные сигналы. Для автомата Мура вопрос кодирования выходных сигналов не принципиален, а правило их кодирования для автомата Мили будет изложено в конце этого параграфа. Пять вершин графа определяют память автомата из 3-х триггеров. Тип триггера: синхронные D- и JK- триггеры динамического типа.

1. Кодирование с ослабленной зависимостью от входных сигналов. Определение и применение 15/43Теория автоматов. Модуль Определение Кодирование с ослабленной зависимостью от входных переменных X={x k } предусматривает размещение подмножества состояний автомата, образованного всевозможными переходами из состояния a m, в одном столбце или строке карты Карно. Вариант кодирования по этому способу отображён на карте Карно, из которой видно, что для данного графа не удалось выполнить размещение подмножеств смежных состояний автомата только в строке (или только в столбце) для состояний «4» и «3». Применение

2. Определение приоритетного кодирования логически смежных состояний 16/43Теория автоматов. Модуль 5 Правило 1. Два состояния автомата из которых возможны переходы в одно и тоже третье состояние, называются логически смежными состояниями (ЛСС-I). Правило 2. Два состояния, в которые может быть осуществлён переход из одного какого-либо состояния, также называются логически смежными (ЛСС-II). При экономичном кодировании ЛСС должны кодироваться соседними кодовыми комбинациями (т.е. различаться значением одного триггера). Если при кодировании нельзя удовлетворить всем условиям смежности, то приоритет отдаётся ЛСС, определённым по 1-му правилу (ЛСС-I). Логически- смежные состояния по 1-му правилу (k, l) Логически- смежные состояния по 2-му правилу (j, s) Логически-смежные состояния по 1-му и 2-му правилам (k, l) Правило 1 Правило 2 Правило 1 и 2

Пример применения приоритетного кодирования логически смежных состояний. 17/43Теория автоматов. Модуль 5 Для рассматриваемого графа: ЛСС-I: (a 1,a 3 ), (a 2,a 5 ), (a 1,a 2,a 4 ЛСС-II: (a 2,a 5 ), (a 4,a 5 ), (a 1,a 4 ), (a 3,a 5 ). В случае, если в группе оказываются не 2 состояния, а три и больше, то они по возможности должны находится в соседних клетках карты Карно. Ниже представлена карта Карно с возможным вариантом кодирования (расположение состояний (a 3,a 5 ) не являются удачными)

Способ кодирования состояний автомата, минимизирующий суммарное число переключений элементов памяти на всех переходах (Д. З. Мороз) 18/43Теория автоматов. Модуль 5 Введём в рассмотрение функцию которая характеризует меру суммарного числа переключений триггеров на всех переходах автомата. Здесь d ij – кодовое расстояние между комбинациями k(a i ) и k(a j ), а p ij -число различных переходов между смежными состояниями a i и a j. Кодовое расстояние (расстояние Хэмминга) – определяется числом двоичных разрядов, на которых кодовые комбинации отличаются друг от друга. Метод рассмотрим на примере ранее введённого графа. 1. Выпишем матрицу Т из всех пар смежных состояний автомата, для которых p ij 0, и i

Кодирование состояний автомата (продолжение мет. Мороза) 19/43Теория автоматов. Модуль 5 2. Составим матрицу М путём упорядочивания строк матрицы Т в соответствии с нормирующими множителями. После первой пары (45) выбирается пара имеющая общий компонент с парой из первой строки и, имеющая наибольший вес (15). Затем выбирается пара, имеющая общий компонент с одной из первых 2-х пар (25) и заносится в третью строку и т. д. 3. Производится кодировка состояний элементов первой строки (45) с помощью карты Карно, используя для этого соседние клетки с кодовыми комбинациями, содержащими наименьшее числом «1» В силу упорядоченности матрицы М, вторая строка (пара (15) ) будет содержать одно не закодированное состояние (1). Его кодировка осуществляется на основе минимизации частичной функции W 1 по частичной матрице М 1, в которую входят пары с состоянием (1). Поскольку в матрице М 1 имеется только одна пара с известной кодировкой состояния, то кодировка состояния осуществляется из минимизации функции W 1 =d 15 p 15 на одном переходе.

Кодирование состояний автомата (окончание мет. Мороза) 20/43Теория автоматов. Модуль В матрице М вычёркиваем строки, в которых оба состояния являются закодированными и приступаем к кодировке состояний первой не вычеркнутой пары (25). Принимаем: При этом, получим: 6. Окончательно. Принимаем: При этом получим:

Оценка эффективности данных способов кодирования 21/43Теория автоматов. Модуль 5 Для сравнительного анализа способов кодирования взят один и тот же граф автомата с 5-ю вершинами, рассмотренный выше. Синтез КС, произведённый классическим способом здесь опущен, результаты сложности схем сведены в таблицу. Тип триггера: синхронные D- и JK- триггеры динамического типа. Способ кодирования Сложность КС сигналов возбуждения JK - триггерD- триггер 1. Кодирование с ослабленной зависимостью от входных сигналов Кодирование логически смежных состояний Способ, минимизирующий суммарное число переключений элементов памяти на всех переходах автомата Случайное кодирование Применение любого из методов экономичного кодирования существенно упрощает сложность КС, формирующей сигналы возбуждения триггеров памяти автомата. 2. Делать вывод о наиболее эффективном из рассмотренных методов нельзя в силу зависимости качества кодирования (для любого из методов) от топологии графа автомата. Однако, наиболее универсальными из простых способов следует признать 2-ой и 3-ий способы. 3. Использование D-триггера в качестве элемента памяти автомата не рационально. Причина в том, что это единственный тип триггера, который для сохранения «единичного состояния» требует в момент синхронизации (фронта С-сигнала) наличия единичного D- сигнала на своём входе. Поэтому, при кодировании состояний автомата выполненного на D- триггерах, используются в первую очередь комбинации с наименьшим числом «1».

Рекомендации по кодированию выходных сигналов автомата 22/43Теория автоматов. Модуль 5 Кодирование выходных сигналов мало влияет на сложность комбинационной схемы (КС-2), однако рекомендуется придерживаться следующего правила: выходной сигнал w l, имеющий наибольшую частоту появлений в таблице выходов, должен кодироваться кодовой комбинацией с наименьшим числом «1». a1a1 a2a2 a3a3 z1z1 a 3 /w 2 a 1 /w 1 z2z2 a 3 /w 3 a 2 /w 2 z3z3 a 2 /w 4 a 2 /w 1 Wy1y1 y2y2 w1w1 00 w2w2 01 w3w3 10 w4w4 11 Таблица переходов и выходов автомата, использованная ранее для демонстрации классического метода синтеза структурного автомата. Wy1y1 y2y2 Частота w1w1 003 w2w2 012 w3w3 101 w4w4 111 W = {w 1 w 2 w 3 w 4 } Частота появления { } сигнала w l в таблице переходов и выходов. Было выполнено Рекомендуется к выполнению (совпало)

Пример синтеза формирователя импульсов как автомата Мура 23/43Теория автоматов. Модуль 5 Работа формирователя импульсов задана временной диаграммой, из которой следует, что период генерации периодической последовательности сигналов составляет 5 периодов синхросигнала Clock. Это позволяет определить граф автомата Мура с пятью состояниями (рис. а). 1. Определение выходных сигналов из соотношений: у 1 = a 4 v a 5, y 2 = a 1 v a 4, y 3 =Clock & ¬y Определение числа триггеров в памяти автомата (их будет три). Выбор типа триггера (пускай это будет Т-триггер ) и кодирование состояний автомата каким-либо методом экономичного кодирования. Техническая реализация схемы, полученная после выполнения указанных шагов, будет иметь следующий недостаток. На сигналы у 1 и y 2 в момент перехода автомата из одного состояния в другое будeт накладываться импульсs помех, вызванные переходными процессами смены состояний триггеров памяти. Clock y y y РИ Clock 1 6(1) y1y1 y2y2 y3y3 Стандартный подход к синтезу схемы автомата включает следующие действия:

Продолжение синтеза формирователя импульсов 24/43Теория автоматов. Модуль 5 Принимаем следующий подход, лишённый отмеченных недостатков, но игнорирующий рекомендации по экономичному кодированию состояний автомата. Пускай сигналы y 1 и y 2 представляют собой выходы триггеров Q 1 и Q 2 соответственно. Тогда состояния этих триггеров для каждого состояния будут определяться соответствующими значениями из временной диаграммы. Состояние третьего триггера должно обеспечить различие кодовых комбинаций для состояний а 2 и а 3 и, по возможности, оптимизировать общий результат кодирования (т. е. по возможности реализовать переходы с минимальным кодовым расстоянием). Время tt+1t amam Q 1 /y 1 Q 2 /y 2 Q 3 Q 1 Q 2 Q 3 T1T2T3T1T2T Выполнив минимизацию для сигналов возбуждения Т 1, Т 2 и Т 3, получим:

Формирователь управляющей импульсной последовательности 25/43Теория автоматов. Модуль 5

Регистры и их классификация 26/43Теория автоматов. Модуль 5 Регистром называется устройство, предназначенное для запоминания многоразрядных слов, а также для выполнения над ними некоторых логических преобразований. Регистр представляет собой совокупность триггеров, число которых соответствует числу разрядов в слове, и КС, обеспечивающую выполнение некоторых микроопераций: - установка регистра в «0», - приём слова из другого регистра (сумматора и т. д. ), - считывание слова из регистра, - сдвиг хранимого слова вправо или влево на требуемое число разрядов, - преобразование последовательного кода слова в параллельный и наоборот, - выполнение поразрядных логических операций: Здесь i – разряд слова, хранящегося в регистре и слова А, находящегося на входной шине, * - конкретный тип логической операции. По количеству линий передачи для переменных регистры делятся на однофазные и парафазные (две линии на одну переменную), однако главным классификационным признаком является способ приёма и выдачи данных. По этому признаку различают: параллельные, последовательные и параллельно-последовательные регистры. В параллельных регистрах приём и выдача слова производится для всех разрядов слова одновременно и их основная функция – хранение слова (регистры памяти). В последовательных регистрах слова принимаются и выдаются разряд за разрядом, их называют сдвигающими, поскольку тактирующие сигналы перемещают слово в разрядной сетке регистра. Последовательно – параллельные регистры имеют одновременно входы для последовательного и параллельного приёма (выдачи) и могут выполнять взаимные преобразования последовательных кодов в параллельные и наоборот.

Регистры памяти 27/43Теория автоматов. Модуль 5 Регистр памяти – простейший тип регистра с параллельным вводом/выводом данных и представляют собой, по существу, набор триггеров с независимыми информационными входами (разрядными схемами) и общим тактовым входом На рисунке представлена схема регистра на RS- триггерах, оперирующего парафазным кодом данных. Приём данных осуществляется стробирующим импульсом, подаваемый на синхровходы RS-триггеров. Парафазный код требует наличие для одного разряда двух физических линий, что характерно при использовании в регистрах памяти RS- и JK- триггеров. Впрочем, если перед каждым приёмом числа, осуществлять сброс разрядов регистра в 0, то парафазный код можно заменить однофазным, который необходимо задавать только на S -входы RS- триггеров. Однако, в этом случае, приём информации в регистре будет осуществляться за два такта.

Триггеры памяти на динамических D-триггерах 28/43Теория автоматов. Модуль 5 В современных вычислительных устройствах в регистрах памяти используются как правило синхронные D-триггеры, как статические (тактируемые импульсом), так и динамические. Регистры на D-триггерах используют для передача данных однофазный код, что является их несомненным преимуществом. На слайде приведены УГО триггеров памяти на динамических D-триггерах: 155 (533, 531, 555)TM8 и ** ТМ9 (SN**175 и SN**174). Данные схемы содержат набор из D-триггеров (4 и 6), имеющих общие входы сброса и тактового импульса С. В ИС ТМ8 число триггеров 4, у каждого есть выходы Q и ¬Q. ИС ТМ9 содержит шесть D-триггеров, у которых только один выход Q. SN175 SN174

Схема регистра памяти TM8 (SN175 ) на D-триггерах 29/43Теория автоматов. Модуль 5 Принцип действия (записи данных) регистров данного типа, срабатывающих по фронту тактового сигнала С ничем ни отличается от принципа действия D- триггера. По положительному фронту тактового сигнала С каждый из выходов регистра устанавливается в тот уровень, который был в этот момент на соответствующем D- входе регистра, и сохраняется таковым до прихода следующего положительного фронта сигнала С.

Универсальный регистр на D-триггерах динамического типа (155, 133ИР13 – SN74 хх 198) 30/43Теория автоматов. Модуль 5 D R - вход для последовательного сдвига вправо (в сторону мл. раз.) Режим работы Тактирующий вход Сброс: S 0 =*, S 1 =*, T=*, ¬R=0 Параллельный ввод слова A={a i } D L - вход для последовательного сдвига влево (в сторону ст. раз.) Ст. разряд (Most significant bit – MSB) Мл. разряд (Least significant bit – LSB) Параллельный вывод слова S 0 S 1 (¬R =1, T= )Режим работы 0 Хранение 0 1Последовательный ввод со сдвигом влево 1 0Последовательный ввод со сдвигом вправо 1 Параллельная загрузка слова A={a i }

Синтез универсального регистра на D-триггерах динамического типа, выполняющего три микрооперации. 31/43Теория автоматов. Модуль 5 Режим работы Тактирующий вход Сброс: S 0 =*, S 1 =*, T=*, ¬R=0 Параллельный ввод слова A={a i } D L - вход для последовательного сдвига влево (в сторону ст. раз.) Ст. разряд (Most significant bit – MSB) Мл. разряд (Least significant bit – LSB) Параллельный вывод слова S 0 S 1 (¬R =1, T= )Режим работы 0 Хранение 0 1 Параллельная загрузка слова A={a i } 1 0Последовательный ввод со сдвигом влево 1 Запрещённый режим

Синтез i -разряда универсального регистра 32/43Теория автоматов. Модуль 5 Структура n -разрядного регистра представляется набором из n идентичных схем, поэтому синтез регистра сводится к синтезу его i- го разряда Режим Вход. сигналы Состояние i-го разр. Di tDi t S o S 1 a i Q i-1 Qi tQi t Q i t / XXXXXXXX XXXXXXXX Функционирование i-го разряда регистра задано таблицей. Столбец таблицы для сигнала возбуждения D-триггера заполнен в соответствии с его характеристическим уравнением

Уравнение работы i-го разряда регистра 33/43Теория автоматов. Модуль 5 Режим Вход. сигналы Состояние i-го разрядаDi tDi t S o S 1 a i Q i-1 Qi tQi t Q i t / XXXXXXXX XXXXXXXX ******** Di tDi t a i Q i-1 Q i s 0 s 1

Схема i-го разряда универсального регистра 34/43Теория автоматов. Модуль 5

Счётчики. Закон функционирования суммирующего счётчика 35/43Теория автоматов. Модуль 5 Счётчик – это функциональный узел автоматного типа, предназначенный для регистрации поступающих на его вход числа импульсов и деления их на модуль счёта M.Модуль счёта определяется числом состояний счётчика (M2 n, где n- число двоичных разрядов счётчика). Счётчики классифицируются по признакам: - модуль счёта (двоичный, десятичный, произвольный); - направление счёта (суммирующие, вычитающие, реверсивные); - структурная организация (синхронные и асинхронные). Закон функционирования суммирующего счётчика в режиме прямого счёта: - значения переменной Q i изменяется тогда, когда переменная в соседнем младшем разряде Q i-1 переходит из состояния 1 в 0 (асинхронный принцип); - значения переменной Q i изменяется с приходом очередного импульса тогда, когда переменные во всех младших разрядах Q i-1,…, Q 1 находится в состоянии 1 (синхронный принцип). Число входных импульсов Прямой счёт Обратный счёт Q 4 Q 3 Q 2 Q Для построения счётчиков можно воспользоваться эвристическим алгоритмом исходя из рассмотрения записи последовательности двоичных чисел

Закон функционирования вычитающего счётчика 36/43Теория автоматов. Модуль 5 Закон функционирования для вычитающего счетчика : - значение выходной переменной Q i изменяется, когда переменная в соседнем младшем разряде Q i-1 переходит из состояния «0» в состояние «1» (асинхронный принцип). - значение выходной переменной Q i изменяется при поступлении очередного импульса счета в том случае, когда все переменные в предыдущих младших разрядах Q i-1,..., Q 1 находятся в состоянии «0» (синхронный принцип) Число входных импульсов Прямой счёт Обратный счёт Q 4 Q 3 Q 2 Q

Асинхронные счетчики 37/43Теория автоматов. Модуль 5 Асинхронные счетчики строятся в виде цепочки Т - триггеров со счетным входом (JK- триггер с J=K=1 или D - триггер с инверсной обратной связью (D=¬Q)), когда тактовый вход каждого последующего подключен к выходу Q или ¬Q предыдущего, что зависит как от направления счета, так и от типа тактирующего входа триггера. Ниже представлена схема асинхронного суммирующего счетчика на JK- триггерах и временная диаграмма его работы. Временные диаграммы приведены для случая, когда состояние счётчика было Q 3 Q 2 Q 1 =011 CLK Q 3 Q Q 1

Асинхронный вычитающий счетчик на D- триггерах 38/43Теория автоматов. Модуль 5 Асинхронный вычитающий счетчик на D- триггерах и временная диаграмма его работы. Временные диаграммы приведены для случая, когда состояние счётчика было Q 3 Q 2 Q 1 =101. Если в схеме вычитающего счетчика на D- триггерах тактовые входы триггеров соединить с инверсными выходами предыдущих триггеров, то счетчик станет суммирующим.

Свойства асинхронных счётчиков 39/43Теория автоматов. Модуль 5 Приведённые схемы счетчиков называют последовательными, так как в них каждый триггер переключается выходным сигналом предыдущего. Эти счетчики отличаются простой схемой, но низким быстродействием в режиме регистрации входных сигналов, так как в этом режиме нельзя подавать очередной входной сигнал, пока не зафиксировано предыдущее состояние счетчика. Время установления кода равно t уст = nt зд. тр, где t зд. тр - время задержки переключения триггера. Очевидно, что максимальная частота входных сигналов в режиме регистрации составляет f макс.рег =1/t уст. В режиме деления входных импульсов максимальная частота их поступления будет ограничиваться быстродействием младшего триггера и составит f макс.дел =1/t зд.тр. Второй недостаток состоит в том, что из-за накопления временных сдвигов в разрядах в процессе установления кода, в счетчике возникают на короткие промежутки времени ложные промежуточные состояния, например, смена состояний разделяется на фазы: Поэтому если к выходным разрядам такого счетчика подключить дешифратор, то на его выходах могут появиться ложные сигналы, соответствующие промежуточным фазам перехода счетчика из одного состояния в другое.

Синхронные двоичные счетчики 40/43Теория автоматов. Модуль 5 От названных выше недостатков свободны синхронные счетчики, в которых с приходом очередного импульса осуществляется одновременное переключение тех триггеров, состояния которых должны измениться для формирования нового состояния. Т Т Т Синхронный Т- триггер, тактируемый срезом. Схему синхронного счетчика можно представить обобщенной структурной схемой, включающей триггеры со счетным входом T и комбинационную схему, формирующую функции возбуждения f i для этих счетных входов. В JK- триггерах счетный вход организуется путем соединения входов J и K. Вход управляет режимом работы схемы : - прямой счет, - обратный счет (Up – вверх, Down - вниз). Выходной сигнал переноса/займа CR/BR (Carry/Borrow) может использоваться для наращивания разрядности счетчика.

Уравнения работы синхронного счётчика 41/43Теория автоматов. Модуль 5 В соответствии с синхронным принципом функционирования счётчика, переключение триггера младшего разряда осуществляется с приходом каждого счетного сигнала CLK, а остальных триггеров - только в том случае, когда все триггеры младших разрядов установлены в «1» ( - прямой счет) или в «0» (обратный счет). Следовательно, в общем случае, функция возбуждения f i триггера со счётным входом для синхронного двоичного счетчика может быть определена выражением: Для младшего разряда: f 1 =1. Сигнал переноса/заёма CR/BR может формироваться в двух случаях, а именно, когда в счетчике хранится максимальное значение кода Q n Q n-1 …Q 1 =11… при и минимальное значение кода Q n Q n-1 …Q 1 =00…0 при : Схема 4-разрядного синхронного двоичного счетчика с изменяемым направлением счета (Up-Down-Counter), построенного в соответствии с выражениями (1) и (2) представлена на рисунке в следующем слайде. Дополнительно в схему введен управляющий вход CE (Count Enable - разрешение счета), обеспечивающий возможность наращивания разрядности счётчика путём объединения уже имеющихся схем меньшей разрядности.

Схема синхронного реверсивного счётчика 42/43Теория автоматов. Модуль 5 Схемы TTL: 555, 533ИЕ13 (SN**191), КМОП: 561,564ИЕ11(MC14516). ( - прямой, - обратный).

Временные диаграммы работы 43/43Теория автоматов. Модуль 5 Временные диаграммы формирования переноса - заёма в 4-разрядном синхронном счетчике (CE =1) поясняют особенности формирования переноса в режиме прямого счета и заёма - в обратном, с учетом запаздывания в их формировании относительно тактового сигнала CLK.