Реферат: Автомат цифровой
Федеральное агентство по образованию
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СПО
«БЕЛГОРОДСКИЙ ИНДУСТРИАЛЬНЫЙ КОЛЛЕДЖ»
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОЙ РАБОТЕ
по дисциплине: «Вычислительная техника»
на тему: «Автомат цифровой»
СОДЕРЖАНИЕ
Введение
1. Структурная схема цифрового автомата
2. Алгоритм функционирования цифрового автомата в микрооперациях
3. Структурная схема операционного устройства
4. Синтез цифрового автомата
4.1 Алгоритм функционирования цифрового автомата в микрокомандах
4.2 Граф функционирования цифрового автомата
4.3 Кодирование состояний
4.4 Таблица функционирования
4.5 Функции возбуждения триггеров и формирования управляющих сигналов
4.6 Схема управляющего устройства
4.7 Проверка управляющего устройства
4.8 Проверка операционного устройства n=8; Ai=4;10;9;5;6;7;12;3
Приложение А: КМ 155 ИД 6; К 531 ИЕ 16; К 531 ИЕ 11; К 155 ИМ 6;
К 533 ИР 25
ВВЕДЕНИЕ
Цифровой автомат представляет собой вычислительное устройство или узел, содержащий элементы памяти и выполняющий дискретные преобразования над хранящейся в автомате информацией. Цифровой автомат способен переходить из одного состояния в другое в результате входных информационных воздействий и выдавать выходную информацию, зависящую от своего состояния и входного воздействия.
Сложность цифрового автомата в основном определяется числом состояний и объемов входных воздействий. Чем больше число состояний автомата, тем больше он должен содержать запоминающих элементов для хранения и отождествления своих состояний. Если при проектировании вычислительных устройств ставится задача анализа и синтеза только логических, в том числе арифметических, преобразований без рассмотрения форм и способов хранения исходных, данных и результатов, то такая задача решается на основе булевых преобразований и использования только комбинационных схем. Таким образом, проблема анализа и синтеза цифровых автоматов является более общей, включающей в себя вопросы анализа и синтеза, как комбинационных схем, так и элементов памяти.
Анализ и синтез комбинационных схем основан на использовании определенного элементного базиса. Также и любой сложный автомат содержит определенный элементарный автоматный базис. Сложный автомат, имеющий m состояний, содержит k автоматов с меньшим числом состояний. В пределе самый простой автомат может иметь всего два состояния. Такой автомат можно принять за элементарный базовый автомат. Все элементарные автоматы различаются по организации их входов, т. е. по их реакциям на входные воздействия.
Выходные комбинационные схемы в элементарных автоматах обычно отсутствуют, поэтому их выходы однозначно соответствуют состояниям автоматов. Входные комбинационные схемы элементарного автомата предопределяют его реакцию на тот или иной вид входного воздействия.
/>/>Базисный состав элементарных автоматов дополнительно расширяется числом входов и набором видов входных воздействий.
Базисный автоматный набор может быть сформирован различными способами, но обычно роль базисного набора выполняют триггеры типа SR, JK, D.
Регистровые схемы, рассмотренные представляют собой наборы из n элементарных автоматов, имеющие 2n состояний и не содержащие вообще или содержащие простейшие межразрядные связи.
Вычислительные устройства выполняют дискретные преобразования над числами определенной разрядности и определенного объема, поэтому цифровые автоматы имеют конечное число состояний и относятся к классу конечных автоматов.
Вся входная и выходная информация автоматов – двоично-закодированная.
/>/>Автоматы бывают синхронные и асинхронные. Асинхронные автоматы непосредственно реагируют на любое изменение входного воздействия; в результате изменения их состояний (после воздействий) возбуждаются все цепочки взаимодействия между элементарными автоматами. Поэтому синтез асинхронных автоматов из-за возможности возникновения гонок, соревнований и ложных переключений довольно затруднен. С целью исключения подобных явлений и упрощения синтеза в вычислительных устройствах используются в основном синхронные элементарные автоматы, содержащие входы синхронизации. С их помощью жестко устанавливается последовательность взаимодействия элементарных автоматов, и выбираются только те линии связи, которые должны обеспечивать их взаимосвязь в определенные тактовые промежутки времени. В настоящей курсовой работе рассмотрен принцип построения цифрового автомата с «жесткой логикой», который в массиве данных «А» выбирает элементы равные числу «В» и определяет их количество и сумму.
1. СТРУКТУРНАЯ СХЕМА ЦИФРОВОГО АВТОМАТА
Управляющие автоматы с «жесткой» логикой представляют собой логические схемы, вырабатывающие распределенные во времени управляющие функциональные сигналы. В отличие от управляющих устройств с хранимой в памяти логикой, у этих автоматов можно изменять логику работы только путем переделок схем автомата.
Типичная структурная схема управляющего автомата с «жесткой» логикой показана на рисунке 1. В состав схемы входят регистр кода операции, являющийся частью регистра команд, счетчик тактов, дешифратор тактов и дешифратор кода операции, а также логические схемы образования управляющих функциональных сигналов.
Рисунок 1. Структурная схема цифрового автомата
На счетчик тактов поступают сигналы от блока синхросигналов, и счетчик с каждым сигналом меняет свое состояние. Состояния счетчика представляют собой номера тактов, изменяющиеся от 1 до n.
Дешифратор тактов формирует на t-м выходе единичный сигнал при 1-м состоянии счетчика тактов, т.е. во время j-го такта.
Дешифратор кода операции вырабатывает единичный сигнал на j-м выходе, если используется j-я команда.
Логические схемы образования управляющих функциональных сигналов для каждой команды возбуждают формирователи функциональных сигналов для выполнения требуемых в данном тракте микроопераций.
В общем случае значения управляющих сигналов зависят еще и от оповещающих сигналов, отражающих ход вычислительного процесса.
Серьезным недостатком рассмотренной схемы является одинаковое число трактов для всех команд. Это требует выравнивания числа тактов исполнения команд по наиболее «длинной » команде, что ведет к непроизводительным затратам времени. Чтобы устранить этот недостаток, схемы строят с использованием нескольких счетчиков трактов.
Схема формирования тактовых сигналов (датчик тактовых сигналов) может строиться на основе использования регистра сдвига, по которому двигается одна 1 (регистр с «бегущей единицей»), что не требует использования дешифратора.
Построение управляющих автоматов с «жесткой» логикой формализуется на основе интерпретации микропрограмм, например, на языке микроопераций или в виде графа. По микропрограмме строится соответствующий управляющий автомат типа Мура или Мили.
При синтезе схем автоматов формальным методом приходится решать вопросы оптимального кодирования состояний, минимизации числа состояний автоматов, факторизации выражений, описывающих булевы функции возбуждения и выхода, и ряд других.
2. АЛГОРИТМ ФУНКЦИОНИРОВАНИЯ ЦИФРОВОГО АВТОМАТА В МИКРООПЕРАЦИЯХ
Для решения поставленной задачи в состав операционного устройства цифрового автомата входят следующие элементы: Регистр RG1 – для хранения элементов массива «А», счетчик Сч1 – для счета числа циклов, сумматор SM1 – для сравнения элементов массива с числом «В», сумматоры SM2 и SM3 – для определения элементов суммы массива меньше числа «В», регистры RG2 и RG3 – для хранения суммы элементов массива меньших числа «В», счетчик Сч2 – для счета количества элементов массива меньше числа «В». Алгоритм функционирования цифрового автомата в микрооперациях представлен на рисунке 2.
/>
/>Рисунок 2. Алгоритм функционирования цифрового автомата в микрооперациях
Под действием управляющего сигнала y1 в счетчик Сч1 должен быть установлено нулевое состояние.
Под действием управляющего сигнала y2 регистры RG2 и RG3 должны быть установлены в нулевое состояние.
Под действием управляющего сигнала y3 в Сч1 записываются «n» соответствующее количество элементов проверяемого массива.
Под действием управляющего сигнала y4 в регистр RG1 поочередно записываются в элементы проверяемого массива.
В сумматоре SM1 сравниваются элементы проверяемого массива с числом «В» и форматируется признак x1. Признак Х1=0, если (Ai ≥В), а Х1=1, если Ai<В.
--PAGE_BREAK--Под действием управляющего сигнала y5 содержимое регистра RG1 поступает на входы сумматора SM3, и в сумматорах SM2 и SM3 складывается содержимое регистров RG1 с RG2 и RG3, результат суммирования записывается в регистрах RG2 и RG3.
Под действием управляющего сигнала y6 к содержимому счетчика Сч2 прибавляется 1.
Под действием управляющего сигнала y7 из содержимого счетчика Сч1 вычитается единица, и формируется признак x2. Признак x2=0, если содержимое счетчика Сч2 не равно 0, и x2=1, если содержимое счетчика Сч2 равно 0.
/>/>/>
3. СТРУКТУРНАЯ СХЕМА ОПЕРАЦИОННОГО УСТРОЙСТВА
/>В состав операционного устройства входят следующие микросхемы: регистры – К533 ИР25, сумматоры – К555 ИМ6, счетчики – К555 ИЕ 11, К555 ИЕ 16. Структурная схема операционного устройства представлена на рисунке 3.
/>Рисунок 3. Структурная схема операционного устройства
Под действием управляющего сигнала y1 в счетчике CT2 должен быть организован режим сброса.
Под действием управляющего устройства y2 в регистрах RG2 и RG3 должен быть организован режим сброса.
Под действием управляющего устройства y3 в счетчике CT1 должен быть организован режим параллельной нагрузки, и на входы D должен действовать двоичный код, соответствующий числу n.
Под действием управляющего устройства y4 в регистре RG1 должен быть организован режим параллельной загрузки, и на входы D должны поочередно подаваться двоичные коды, соответствующие элементам проверяемого массива.
В качестве сумматора SM1 используется арифметико–логическое устройство К155ИП3. В нем сравниваются элементы проверяемого массива, с числом «В». Для сравнения в АЛУ должен быть организован режим «вычитания». На выходе Cn+4 формируется признак X1.
Под действием управляющего сигнала y5, элемент массива, равный числу «B», подается на входы A, сумматора SM3, и в регистрах RG2 и RG3 должен быть организован режим параллельной загрузки.
Под действием управляющего сигнала y6 в счетчике Сч.2 должен быть организован режим счета на увеличение.
Под действием управляющего сигнала y7 в счетчике CT1, должен быть организован режим счета на уменьшение.
На выходе переноса при счете на уменьшение TCD формируется признак x2.
4. СИНТЕЗ ЦИФРОВОГО АВТОМАТА
4.1 Алгоритм функционирования цифрового автомата в микрокомандах
В микрокоманды Y можно объединить управляющие сигналы y, под действием которых выполняются микрооперации в различных не связанных между собой блоках, а также управляющие сигналы y последовательность формирования которых в процессе выполнения алгоритма не изменяется. Алгоритм функционирования цифрового автомата представлен на рисунке 4.
Рисунок 4. Алгоритм функционирования цифрового автомата в микрокомандах
Микрокоманда Y1 включает управляющие сигналы y1, y2, y3.
Микрокоманда Y2 включает управляющий сигнал y4.
Микрокоманда Y3 включает управляющие сигналы y5, y6.
Микрокоманда Y4 включает управляющий сигнал y7.
Выполним разметку алгоритма, при которой символами a0обозначим начало и конец алгоритма, символами a1, a2, a3, a4, обозначим операторные блоки.
Символы a0, a1, a2, a3, a4 соответствуют состояниям цифрового автомата.
4.2 Граф функционирования цифрового автомата
Граф функционирования цифрового автомата строится на основе алгоритма функционирования цифрового автомата в микрокомандах. В узлах графа записаны состояния цифрового автомата, стрелками показаны возможные переходы, над стрелками записаны условия переходов. Выделенные стрелки соответствуют безусловным переходам. Граф функционирования цифрового автомата представлен на рисунке 5.
/>/>/>
/>/>/>
/>/>
/>
/>
Рисунок 5. Граф функционирования цифрового автомата
Из состояния a0выполняется безусловный переход в состояние a1. Из состояния a1 выполняется безусловный переход в состояние a2. Из состояния a2 при условии x1 равном 0 выполняется переход в состояние a4, а при условии x1 равном 1 выполняется переход в состояние a3. Из состояния a3, выполняется безусловный переход в состояние a4. Из состояния a4 при условии x2 равном 1 выполняется переход в состояние a0, а при условии x2 равном 0, выполняется переход в состояние a2.
4.3 Кодирование состояний
Для кодирования состояний цифрового автомата выбираем RS-триггеры. Необходимое количество триггеров выбирается из условия минимального n, удовлетворяющего соотношению (1)
/>, (1)
где n – необходимое количество триггеров;
N – количество состояний цифрового автомата.
Для N равного 5, n равно 3. Каждому состоянию цифрового автомата поставим в соответствие комбинацию состояний триггеров. Кодирование состояний цифрового автомата представлено в таблице 1.
Таблица 1. Кодирование состояний
Состояния автомата
Состояния триггера
а
Q2
Q1
Q
a
a1
1
a2
1
a3
1
1
a4
продолжение--PAGE_BREAK--
1
/>/>4.4 Таблица функционирования
Функционирование цифрового автомата можно представить в виде таблицы, построенной на основе графа функционирования. В каждой строке таблицы описывается определенный переход цифрового автомата, и указываются сигналы управления триггерами, необходимые для выполнения данного перехода. Функционирование цифрового автомата представлено в таблице 2.
Таблица 2. Функционирование цифрового автомата
Текущее состояние
Следующее состояние
Условие перехода
Сигналы управления триггерами
a
Q2
Q1
Q
a
Q2
Q1
Q
T2
T1
T
a
a1
1
-
-
-
S
a1
1
a2
1
-
-
S1
R
a2
1
a3
1
1
/>
-
-
S
a2
1
a4
1
/>
S2
R1
-
a3
1
1
a4
1
-
S2
R1
R
a4
1
a
/>
R2
-
-
a4
1
a2
1
/>
R2
S1
-
Для перевода RS-триггера из “0” состояния в “1” необходимо активный логический уровень подать на вход установки в единичное состояние S. Для перевода RS-триггера из “1” состояния в “0” необходимо активный логический уровень (0 или 1) подать на вход R.
4.5 Функции возбуждения триггеров и формирования управляющих сигналов
В каждом состоянии цифрового автомата формируется соответствующая микрокоманда Y. Для микрокоманд Y можно записать логические выражения (2-5).
Y1 = а1 (2)
Y2 = а2 (3)
Y3 = а3 (4)
Y4 = а4 (5)
Логические выражения для сигналов управления триггерами запишем как простую дизъюнкцию конъюнкций текущего состояния и условия перехода, при которых эти сигналы получаются. Сигналы управления триггерами формируются в соответствии с логическими выражениями (6-11).
/>(6)
/>(7)
/>(8)
/>(9)
продолжение--PAGE_BREAK--
/>(10)
/>(11)
4.6 Схема управляющего устройства
Управляющее устройство состоит из дешифратора (К 553 ИД 6); комбинационного узла, построенного с помощью логических выражений (6-11) и трех RS-триггеров с инверсными входами (микросхема К 555 ТР 2).Схема управляющего устройства представлена на рисунке 6.
/>Рисунок 6. Схема управляющего устройства
Выходы триггеров T1, T2, T3соединены с входами A, A1, A2дешифратора. На выходах дешифратора />формируются инверсии состояний цифрового автомата />.Так как используются выходы />, то в соответствии с таблицей функционирования на вход A3должен действовать уровень логического нуля, поэтому этот вход должен быть заземлен. Выходы дешифратора и линии, по которым поступают признаки x1и x2объединены в “жгут”, провода которого пронумерованы от 1 до 8.
Для построения схемы управляющего устройства использовались микросхемы:
1) DD1 – К 533 ИД 6;
2) DD2, DD3 – К 155 ЛЛ 1;
3) DD4 – К 155 ЛИ 1;
4) DD5 – К 155 ЛЕ 1;
5) DD6 – К 555 ТР 2.
/>4.7 Проверка управляющего устройства
Возможные переходы цифрового автомата представлены в таблице 3.
Таблица 3. Возможные переходы цифрового автомата
S2
R2
S1
R1
S
R
a
1
a1
1
1
a2
S2
R2
S1
R1
S
R
X1=
X1=1
/>
1
1
1
a4
a3
1
1
1
a5
a4
X2=0
X1=1
продолжение--PAGE_BREAK--
1
1
1
a2
a
0+1=1
--PAGE_BREAK--1001
/>1111
--PAGE_BREAK--4+1=5
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--Х
В
В
Х
qn
В
Микросхема К155ИM6
Микросхема ИМ6 — это четырехразрядный быстродействующий двоичный полный сумматор. Он принимает два четырехразрядных слова по входам данных АО...A3 и ВО… ВЗ, а по входу Сn – сигнал переноса. Сумма разрядов входных слов появляется на выходах ∑0… ∑3. На выходе Cn+1 выделяется сигнал переноса. Имеется схема ускоренного переноса (СУП).
Сумматор может работать со словами как положительной, так и отрицательной логики.
Суммирование происходит по уравнению:
Cn + 20(AO + BO) + 21(Al + Bl)+22(A2 + B2) + 23(A3 + B3) = 20Σ 0 + 21Σ1 + 22Σ2 + 23Σ3 + 24Сn+1.
Состояния сумматора приведены в таблице.
Таблица A.5 Суммирование чисел микросхемой ИМ6
Данные на входе
Cn
А
А0
А0
А0
В0
В0
В0
В0
Σ0
Σ
Σ
Σ
Cn+1
Цифровой
результат
Электрические уровни
1
1
1
1
1
1
1
Активный уровень «1»
1
1
1
1
1
1
1
10+9=19
Активный уровень «0»
1
1
1
1
1
1
1
Cn+5+6=↑2