50267 (Структурные автоматы), страница 4
Описание файла
Документ из архива "Структурные автоматы", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "50267"
Текст 4 страницы из документа "50267"
Q(t+1)=d(Q(t), D(t))= DQ v D
= D.
Триггер типа Т изменяет свое состояние только при подаче на его вход «1». Это триггер со счетным входом. Его характеристическое уравнение имеет вид:
Q(t+1 )=d(Q(t), Т(t))= 
Q v T .
-
4.2 Элементы памяти с двумя информационными входами
Триггеры с двумя информационными входами имеют различное построение в зависимости от режимов использования имеющихся входов. Основными, наиболее распространенными двухвходовыми триггерами являются RS-триггер, JK-триггер, синхронизированный D-триггер. Рассмотрим подробнее каждый из них.
RS-триггер
Название этого элемента происходит от английских слов «set-reset» - «установка-сброс». Он имеет два установочных входа: S -установка в 1, R - установка в ноль (сброс). Работа описывается таблицей переходов (табл. 21). На 6 и 7 наборах функция не определена, т.к. считается, что нет необходимости устанавливать данный триггер в положение «1» и «О» одновременно. Таким образом, входная комбинация 11 для RS-триггера является запрещенной и не должна возникать в реальных условиях работы.
Характеристическое уравнение после его преобразования и минимизации имеет вид:
Q(t+1 )=d (Q(t), R(t), S(t))= 
Q v S.
Это соотношение показывает, что при нулевом сигнале на входе «установка в ноль» (R=0) RS-триггер является дизъюнктором накапливающего типа. Он осуществляет логическое сложение содержимого триггера Q(t) и сигнала S(t), после чего результат операции записывается вместо первого слагаемого. В частном случае, при обнуленном триггере, осуществляется запись в триггер той информации, которая поступила на вход S. Условное графическое обозначение RS-триггера представлено на рис. 7.а).
а) б) в)
Рисунок 7- Условное графическое обозначение триггеров:
а) RS-триггер; б) JK-триггер; в) синхронизированный D-триггер.
J-K-триггер
Он имеет два установочных входа: J - установка в 1, К - установка в ноль. Работа описывается таблицей переходов (табл. 22). Для него не существует запрещенных наборов входных сигналов.
Характеристическое уравнение после его преобразования и минимизации имеет вид:
Q(t+1)=d(Q(t), J(t), К (t)) = KQ v QJ.
Из этого соотношения следует, что JK-триггер является универсальным, имеющим два режима работы.
1) Режим записи и хранения информации, пришедшей по входу J, если триггер заранее был обнулен, поскольку работа обнуленного JK-триггера описывается уравнением RS-триггера. Данный режим называется RS-режимом.
2) Режим счета, который возникает при обеспечении одинаковых сигналов на обоих входах. Поскольку такой режим описывается уравнением, аналогичным уравнению Т-триггера, то его можно назвать Т-режимом. Условное графическое обозначение JK-триггера представлено на рис. 7.б.
D-триггер
Триггер имеет также 2 входа: информационный (D) и синхронизирующий (С). Функция на выходе триггера принимает значение информационного сигнала, если есть разрешающий сигнал по входу C (С=1). При отсутствии разрешающего сигнала (С=0), значение функции замораживается, т.е. остается равным содержимому триггера на предыдущем такте. Работа описывается таблицей переходов (табл. 23.).
Характеристическое уравнение триггера имеет вид:
Q(t+1 )=d(Q(t), D(t), С(t))= 
Q v DC.
Из чего следует, что D-триггер является переключателем накапливающего типа: он пропускает на выход либо сигнал, приходящий по условной шине D, либо сигнал, приходящий по условной шине Q(t), в зависимости от значения управляющего сигнала С. Условное графическое обозначение триггера представлено на рис. 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 | |||
| 12 | 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;
