Структурные автоматы

зависимости от значения управляющего сигнала С. Условное графическое обозначение триггера представлено на рис. 7.в.


4.3 Матрица переходов элемента памяти


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

Для каждого из 4-х возможных переходов элементарного автомата (00, 01, 10, 11) всегда найдется значение входного сигнала, равное 0 или 1, которое вызывает данный переход. Если элементарный автомат имеет 2 или более входов, то на некоторые переходы значения входных сигналов, действующих на одном или другом входе, оказываются несущественными.

Количество строк матрицы всегда равно 4 (по количеству возможных переходов), количество столбцов равно числу входных сигналов. Элемент матрицы bisk представляет собой значение входного сигнала xk под действием которого элементарный автомат перейдет из состояния i в состояние s. При этом bisk всегда равняется 0 или 1, или неопределен, если он не влияет на данный переход.

Матрица переходов элементарного автомата составляется по таблице переходов.

Рассмотрим пример построения матрицы переходов триггера.

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


Структурные автоматы


Полная таблица переходов триггера, построенная по сокращенной, представлена в таблице 25. По полной таблице переходов запишем комбинации входных сигналов, соответствующих всем возможным переходам (табл. 26.) Таким образом:

1. Для перехода "0-0" Х=0, Y может быть равен 0 или 1

2. Для перехода "0-1" Х=1, Y может быть равен 0 или 1

3. Для перехода "1-0" Х может быть равен 0 или 1, а Y=0.

4. Для перехода "1-1" Х может быть равен 0 или 1, а Y=1.

Тогда матрица переходов триггера запишется в виде:


0-0 0 b1
0-1 1 b2
1-0 b3 0
1-1 b4 1

где b1,b2,b3,b4 - произвольные сигналы (0 или 1).

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


Структурные автоматы


С учетом доопределений входных переменных матрицы переходов некоторых стандартных триггеров имеют вид (таб. 28.)


Таблица 28.Матрицы переходов триггеров

Триггер-D Триггер-Т Триггер-RS Триггеp-JK
Q(t) Q(t+1) D Q(t) Q(t+1) Т Q(t) Q(t+1) R S Q(t) Q(t+1) К J
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 1 0 1 0 1 0 1 0 1
1 0 0 1 0 1 1 0 1 0 1 0 1 0
1 1 1 1 1 0 1 1 0 0 1 1 0 0


Кодирование состояний и выходов автомата и сложность комбинационных схем

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

В рассмотренном ранее примере коды состояний автомата принимали значения: a1=00, a2=01, а3=11. Если принять коды: a1=01, а2=01, а3=00, то таблица переходов структурного автомата примет вид (табл. 29).

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


Таблица 29


ZlZ2
a1a2 00 01 10
01 10 00 10
10 - 01 00
00 01 - 00

Структурные автоматы;

Структурные автоматы;


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

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

Алгоритм весового метода кодирования:

1. Каждому выходному сигналу у, ставится в соответствие целое число Pi, равное числу появлений сигнала уi в таблице выходов автомата.

2. Числа Pi сортируются по убыванию.

3. Выходной сигнал yi с наибольшим весом (Pi max) кодируются кодом, содержащим все 0 (00...00).

4. Следующие L выходных сигналов (где L- число разрядов в двоичном векторе выходного сигнала) по списку убывания веса (см п. 2) кодируются кодами, содержащими одну 1 (00...01, 00...10,... ,10...00).

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

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

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

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

При таком критерии уменьшается сложность схем, реализующих дизъюнкции на входах элементов памяти, т.е. минимизируется комбинационная схема автомата. Для оценки кодирования вводится коэффициент эффективности кодирования:


Kэф= W/P;


где Р - общее количество переходов автомата,

W - весовая функция : W=tij

где tij- расстояние Хэмминга между кодами состояний аi и аj, равное числу элементов памяти, изменяющих свое состояние на данном переходе.

Отметим, что при определении весовой функции суммирование производится по всем переходам автомата. Коэффициент эффективности позволяет оценить сложность комбинационной схемы автомата: чем меньше его значение, тем меньше сложность комбинационной схемы, и оптимальный вариант - Kэф=1.

Алгоритм состоит из следующих шагов:

1. Построить матрицу М, составленную из всех пар номеров (ar, br) переходов автомата.

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

3. Закодируем состояния из первой строки матрицы М следующим образом: Ka1=00...00, Kb1=00...01.

4. Вычеркнем из матрицы М первую строку с закодированными состояниями. Получим матрицу М'.

5. В начальной строке матрицы М' закодирован один элемент. Выберем из первой строки матрицы М' незакодированный элемент и обозначим его .

6. Построим матрицу M, выбрав из матрицы М' строки, содержащие у. Пусть В={1,2,...,f,...,F} - множество элементов из матрицы My, которые уже закодированы. Их коды обозначим через К1,К2,...Структурные автоматы,Кf,...,КF соответственно.

7. Для каждого Кgf (f=1, 2,...,F) найдем C1gf - множество кодов, отстоящих от Кgf на расстояние Хэмминга, равное 1 и еще не занятых для кодирования состояний автомата. Построим множество Структурные автоматы.

Если D1 =0, то строим новое множество Структурные автоматы, где Структурные автоматы - множество кодов, у которых кодовое расстояние с кодом Kf равно 2. Если и D2 =0, строим D3 и т.д., пока не найдем Структурные автоматы. Пусть Структурные автоматы.

8. Для каждого Кg находим wgf=|Kg- Kf|2 - расстояние Хэмминга между Кg и всеми используемыми кодами Kf(f=1, 2, ...,F).

9. Находим Структурные автоматы

10. Из Структурные автоматы выбираем К, у которого Wg=Wg min. Элемент у кодируем кодом К.

11. Из матрицы М' вычеркиваем строки, в которых оба элемента закодированы, в результате чего получаем новую матрицу, которую также обозначаем М’. Если в матрице М' не осталось ни одной строки, переходим к п. 12, иначе к п. 5.

12. Вычисляем функцию Структурные автоматы где tij=|Kj-Kj|2.

13. Конец.

Оценкой качества кодирования по рассмотренному алгоритму может служить число K=W/P, где P - число переходов в автомате. Очевидно, что K>=1, причем, чем меньше значение K, тем лучше результат кодирования.

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


Структурные автоматы


1. Строим матрицу М:

Кодируем первую строку: K1=00;K2=01;

2. Вычеркиваем из матрицы М 1-ю строку (1-3) и 6-ю строку (3-1). Получаем матрицу М', в первой строке которой незакодирован элемент 4. Обозначим =4 и запишем матрицу M,. В матрице M закодированы 1 и З: В={1,3}={00,01} Структурные автоматы Находим W:


W10=|00| |10|=3; W11=|00| |11|=3;

|10|+|01| |11|+|01|


Выбираем K4=10.

Вычеркнем из М' строку (1-4). Получим новую матрицу М', в первой строке которой не закодирован элемент 2. Обозначим g=2 и запишем матрицу М2. В матрице М2 закодированы элементы 3, 4:


ВСтруктурные автоматы


Структурные автоматы


Вычислим K=W/P=9/8=1,125.



6. Обеспечение устойчивости функционирования цифровых автоматов. Гонки в автоматах


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

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

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

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

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

Если в процессе перехода из состояния аm в состояние аs под действием входного сигнала xi автомат может оказаться в некотором промежуточном состоянии (аi, аk) в зависимости от того, какой из элементов памяти выиграл состязания, но, затем, при этом же входном сигнале перейдет в состояние аs, то такие состязания называются допустимыми, или не критическими. Но если произойдет переход в состояние аk (не предусмотренное графом переходов автомата) и правильность работы автомата нарушается, то такие состязания называются недопустимыми (критическими) или гонками. Пусть автомат должен выполнить переходы, изображенные на рис. 8.


Структурные автоматы

Рисунок 8


Возможны следующие ситуации:

а) если очередной синхросигнал на входы элементов памяти автомата поступает раньше, чем кончились переходные процессы в его комбинационной схеме возбуждения и элементах памяти после поступления входного сигнала хi, то возможно неправильное формирование сигнала возбуждения на входе одного или нескольких элементов памяти автомата, т. е. автомат может вместо перехода из состояния аm в состояние аs по входному сигналу xi осуществить ложный переход в некоторое состояние аt по тому же самому входному сигналу xi;

б) если длительность входного сигнала хi превышает длительность перехода автомата из состояния аm в состояние аs, то автомат может (при поступлении очередного синхросигнала) проскочить состояние аs и попасть сразу в состояние аk за счет двойного срабатывания автомата по входному сигналу хi. Иными словами, состояние аs может оказаться неустойчивым.


6.1 Методы устранения гонок в автоматах


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

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

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

Однако использование двойной памяти автомата приводит к замедлению работы автомата. Если обычно период синхросигналов выбирается из расчета, что сигнал возбуждения элемента памяти успеет пройти по самой длинной цепочке логических элементов и переключить элемент памяти, то здесь период нужно удлинить по крайней мере на 3t где t- задержка распространения сигнала в логическом элементе (1t- на инвертор и 2t - на второй элемент памяти).

В случаях, когда из соображений быстродействия двухэтажную память использовать нельзя, прибегают к многофазной системе тактирования входных сигналов автомата. Так, для случая двухфазной синхронизации синхросериями CC1 и CC2 вместо одного входного сигнала xi, (рис. 8) используются два разных: хi • СС1 и xi • СС2 (рис. 10).


Структурные автоматы

Рисунок 9


Структурные автоматы

Рисунок 10


Таким способом устойчивость функционирования автомата обеспечивается автоматически. При двухфазной синхронизации необходимо, чтобы все дуги графа переходов автомата можно было бы разметить символами CC1 иCC2 так, что для любой вершины графа все выходящие из нее дуги отмечались бы символом одной синхросерии (например, СС1, а все дуги, заходящие в ту же вершину графа переходов автомата,— символом другой синхросерии (например, СС2). Если граф переходов автомата содержит контур нечетной длины, то такая разметка невозможна.

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

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

Если при переходе автомата из одного состояния в другое, должны переключиться сразу несколько элементов памяти, то между ними начинаются гонки, (состязания), что может привести к неправильной работе автомата. В самом деле, при переходе автомата из состояния ai; в состояние aj на некоторый, хотя и очень короткий, промежуток времени может возникнуть промежуточное состояние автомата, отличное от ai и aj. Например, при переходе из ai (0110) в aj (1010) изменяют свое состояние два первых элемента памяти. Из-за состязаний может возникнуть состояние 1110 (или 0010), которое может привести к изменению состояния третьего или четвертого элемента памяти.

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

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

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

Отметим, что проблема состязаний и некоторые другие вопросы обеспечения устойчивости работы автоматов возникли лишь с появлением потенциальной элементной базы. Используемая ранее (в ЭВМ второго поколения) импульсно-потенциальная элементная база предусматривала применение статических триггеров со встроенной задержкой.

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

Вывод


В процессе выполнения курсовой работы мы ознакомились с:

- основными понятиями структурных автоматов;

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

- теоремой Глушкова о структурной полноте;

- основными этапами канонического метода структурного синтеза;

- примерами канонического метода структурного синтеза;

- кодированием состояний и выходов автомата и сложностью комбинационных схем;

- обеспечением устойчивости функционирования цифровых автоматов;

- гонкой в автоматах;

- методами устранения гонок в автоматах.


Литература


1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа” 1987.

2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.

3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.

4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: