close

Вход

Забыли?

вход по аккаунту

?

Mishyra2

код для вставкиСкачать
Министерство образования и науки российской федерации
Федеральное государственное автономное образовательное
учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ЦИФРОВЫЕ АВТОМАТЫ.
СТРУКТУРНЫЙ СИНТЕЗ
АВТОМАТОВ МИЛИ И МУРА
Методические указания
к выполнению контрольной работы
Санкт-Петербург
2014
Составитель – кандидат технических наук, доцент О. В. Мишура
Рецензент – кандидат технических наук, доцент В. П. Попов
Приведены программа и методические указания к выполнению
контрольной работы по одному из разделов дисциплины «Цифровые
автоматы», связанной со структурным синтезом конечных автоматов.
Предназначены для студентов дневной формы обучения, обучающихся по направлению 230400, (квалификация – бакалавр).
Подготовлены кафедрой информационно-сетевых технологий и
рекомендованы к изданию редакционно-издательским советом СанктПетербургского государственного университета аэрокосмического
приборостроения.
Корректор Т. В. Звертановская
Компьютерная верстка Н. Н. Караваевой
Сдано в набор 23.10.14. Подписано к печати 26.12.14. Формат 60×84 1/16.
Бумага офсетная. Усл. печ. л. 1,2. Тираж 100 экз. Заказ № 682.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2014
1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ,
ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
Программа дисциплины «Цифровые автоматы» составлена в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования по направлению
230400 «Информационные системы и технологии», профили:
230403 – Информационные технологии в дизайне,
230404 – Информационные технологии в медиа индустрии,
230406 – Информационные технологии в бизнесе.
Квалификация – бакалавр.
Программа включает следующие разделы:
1. Машинная арифметика.
2. Аналитическое представление функций алгебры логики.
3. Введение в теорию автоматов.
4. Введение в теорию графов.
Целью преподавания дисциплины «Цифровые автоматы» является ознакомление с классическими математическими моделями
систем обработки дискретных сигналов.
В области воспитания личности в рамках подготовки по данной дисциплине является формирование основ общекультурных и
профессиональных компетенций для приобретения качеств, необходимых создателю новых приборов и технологий, таких как целеустремленность, организованность, трудолюбие, ответственность,
гражданственность, коммуникативность и др.
Для реализации целей изучения дисциплины необходимо выполнение следующих задач:
– ознакомление студентов с основами машинной арифметики;
– ознакомление студентов с основами алгебры логики, аналитического представления функций алгебры логики, минимизацией
логических функций;
3
– ознакомление студентов с теорией графов и ее практическим
использованием;
– представление о современном состоянии научных проблем по
организации цифровых автоматов;
– навыки работы с технической литературой.
По окончании изучения дисциплины студент должен знать основы машинной арифметики, алгебру логики, основы теории графов,
типы триггеров; уметь использовать машинные коды, функции алгебры логики, диаграммы Вейча–Карно, универсальные базисы;
иметь навыки минимизации логических выражений.
В соответствии с учебным планом общая трудоемкость дисциплины, изучаемой в II семестре студентами очной формы обучения,
квалификация – бакалавр, составляет 68 часов. Из них лекции – 34
часа, практические занятия – 34 часа.
Практические занятия включают решение конкретных задач,
связанных с тематикой основных разделов изучаемой дисциплины.
Примерный перечень тем практических занятий:
– представление чисел в ЦВМ с фиксированной и плавающей запятой;
– машинные коды;
– выполнение арифметических операций для чисел с фиксированной и плавающей запятой в машинных кодах;
– свойства логических переменных и логических функций;
– представление логических функций в совершенных нормальных и нормальных конъюнктивных и дизъюнктивных формах;
– применение диаграмм Вейча–Карно для минимизации логических функций;
– введение в теорию графов.
4
2. КОНТРОЛЬНАЯ РАБОТА
При изучении темы «Введение в теорию автоматов» студентам
предлагается выполнение контрольной работы в аудитории или
в виде домашнего задания. По результатам ее выполнения проверяется качество усвоения студентами части лекционного материала, связанного с тематикой структурного синтеза конечных автоматов.
2.1. Формулировка задания к контрольной работе
Контрольная работа имеет название «Структурный синтез конечных автоматов» и включает следующие пункты, которые должны быть выполнены в процессе решения контрольной работы:
1) задание табличным или графическим способом конкретного
автомата Мили или Мура – этап абстрактного синтеза;
2) определение количества элементов памяти;
3) выбор типа элементов памяти;
4) кодирование внутренних состояний автомата;
5) определение количества структурных входных сигналов, кодирование входных сигналов;
6) определение количества структурных выходных сигналов, кодирование выходных сигналов;
7) определение функций возбуждения памяти табличным или
графическим способом;
8) определение выходных функций – выходных сигналов табличным или графическим способом;
9) перевод функций возбуждения памяти и выходных сигналов
в базисы Шеффера или Пирса;
10) построение логической схемы проектируемого автомата Мили или Мура в заданном базисе.
2.2. Пример выполнения контрольной работы
Варианты заданий к выполнению контрольной работы представлены в табл. 6; 7.
2.2.1. Структурный синтез автомата Мили
Рассмотрим выполнение варианта 25. По данному заданию
необходимо синтезировать автомат Мили с последовательно5
стью изменения состояний в зависимости от значения входного
сигнала zf:
z1: 1, 0, 2, 3, 1;
z2: 0, 1, 3, 2, 0;
со следующими выходными сигналами:
w1 – переход из четного состояния при нечетном zf;
w2 – переход из нечетного состояния при четном zf;
w3 – остальные случаи.
Метод структурного синтеза – графический; тип элементов памяти – RS-триггеры.
Выполнение контрольной работы
На этапе абстрактного синтеза построим граф автомата Мили.
По варианту задания автомат Мили имеет четыре внутренних состояния: 0 → а0, 1 → а1, 2 → а2, 3 → а3; два входных сигнала: z1 и z2;
три выходных сигнала: w1, w2, w3.
Исходя из последовательности изменений внутренних состояний
автомата Мили в зависимости от значений входных сигналов zf под
действием сигнала z1 автомат из a0 переходит в a2, потом в a3, потом
в a1 и снова в a0. Под действием входного сигнала z2автомат из a0
переходит в a1, потом в a3, потом в a2 и снова в a0.
Исходя из задания значений выходных сигналов:
w1 – переход из a0 и a2 под действием z1;
w2 – переход из a1 и a3 под действием z2;
w3 – остальные случаи.
Проанализировав задание к контрольной работе, можно построить граф абстрактного автомата Мили (рис. 1).
w3
z2
а0
а3
z1
w2
z2
w1
w3
z1
w3 z1
w3
w1
z2
z1
а1
z2
а2
w2
Рис. 1. Абстрактный граф автомата Мили
6
Переходим к этапу структурного синтеза.
Определяем количество элементов памяти – RS-триггеров.
R =] log2 (M + 1)[ = ]log2 (3 + 1)[= 2.
Таким образом, в структуре автомата Мили будут два RSтриггера: ТА и ТВ.
Закодируем внутренние состояния автомата. Поскольку имеем
два триггера, то разрядность кодовых комбинаций для внутренних
состояний равна двум. Имеем:
à0 = 00 => AB;
à1 = 01 => AB;
à2 = 10 => AB;
à3 = 11 => AB.
Определим количество структурных входных каналов – разрядность кодовых комбинаций для входных сигналов:
L = ]log2F[ = ]log2 2[ = 1.
Закодируем входные сигналы:
z1 = 0 => x;
z2 = 1 => x.
Определим количество структурных выходных каналов – разрядность кодовых комбинаций для выходных сигналов:
N =]log2 G[=]log2 3[= 2.
Закодируем выходные сигналы:
w1 = 01 => y1y2 ;
w2 = 10 => y1 y2 ;
w3 = 11 => y1y2 .
При кодировке параметров абстрактного автомата исходили из
совпадения индекса параметра с кодовым словом в двоичной системе счисления, т. е. à2 = 10 => ÀÂ; ; w3 = 11 => y1y2 .
Теперь можно построить структурный граф автомата Мили – закодированный граф (рис. 2).
7
y1y2
AB
x
y1y2
x
AB
y1y2 x
x
y1y2
y1y2
x y1y2
y1y2
x
x
AB
x
AB
y1y2
Рис. 2. Закодированный граф автомата Мили
Для определения функций возбуждения памяти, т. е. входных
сигналов триггеров RS ТА и ТВ: SA, RAи SB, RBприведем таблицу переходов триггера RS (табл. 1).
Таблица 1
Q(t)
Q (t + 1)
S
R
0
0
0
–
0
1
1
0
1
0
0
1
1
1
–
0
Теперь, исходя из того, что, например, для перехода триггера ТАиз состояния 0 в состояние 1, т. е. из À â À, нужно (по табл. 1) подать
входные сигналы S A , R A , пометить в структурном графе автомата
Мили (рис. 2) дуги переходов соответствующими парами сигналов S
и R (рис. 3).
Определим сигналы возбуждения памяти SA, RA и SB, RB, которые описываются дизъюнкциями конъюнкций внутренних состояний и входных сигналов:
S À = ABx Ú AÂx Ú ÀBx Ú ABõ .
----
8
----
y1y2
S
–
AB
x
y1y2
A ; SB ,
SA , R
–;
S
B,
–;
S
B,
B
B
SA, RA; –, RB
y1y2
y1y2
AB
–,
R
SA, RA; –, RB
S
B,
B,
R
B
S
B
y1y2
x
x
R
y1y2
A; S
B, –
A;
A;
y1y2 x
x
–,
R
y1y2
R
R
SA , R
x
S
A,
x
AB
A,
x
AB
Рис. 3. Отмеченный структурный граф автомата Мили
Подчеркнутые конъюнкции определяют прочерки, т. е. неопределенные значения сигналов.
S A = Bx Ú Âx; R A = AÂx Ú ABx Ú ABx Ú ÀBx.
----
(1)
----
R A = Âx Ú Bx; (2)
9
SB = A Bx Ú ABx Ú AÂx Ú ÀBx.
----
----
1
SB = Ax Ú Ax; (3)
RB = AÂx Ú ABx Ú ÀBx Ú ABx.
----
----
RB = Ax Ú Ax. (4)
Определим выходные сигналы у1 и у2, которые описываются
дизъюнкциями конъюнкций внутренних состояний и входных сигналов.
ó1 = AÂx Ú ABõ Ú ÀBx ÚABx Ú AÂx ÚABx.
10
ó1 = Â Ú õ. (5)
ó2 = AÂx Ú ABõ Ú ÀÂx Ú ÀBõ Ú ÀBx Ú ABx.
ó2 = B Ú x. (6)
Для построения структурной схемы автомата Мили переведем
выражения (1), (2), (3), (4), (5), (6) в базис Шеффера, используя законы де Моргана:
S A = Bx Ú Âx = (Bx ) * (Âx) = S(S(B, x ), S(Â, x)); (7)
R A = Âx Ú Bx =( Âx ) * (Bx) = S (S(Â, x ), S(B, x)); (8)
SB = Ax Ú Ax = ( Ax ) * (Ax) = S(S ( A, x ), S ( A, x)); (9)
RB = Ax Ú Ax =( Ax ) * (Ax) = S(S( A, x ), S ( A, x)); (10)
y1 = Â Ú õ = Bõ = S(B, õ ); (11)
y2 = B Ú x = Bõ = S(B, õ). (12)
По выражениям (7)–(12) строим структурную схему автомата
Мили в базисе Шеффера (рис. 4).
11
x x
A
A
B
B
&
&
&
S TA A
R
&
A
&
&
&
&
&
&
SТ В
В
В
R
&
&
&
&
y1
y2
Рис. 4. Структурная схема автомата Мили
2.2.2. Структурный синтез автомата Мура
Рассмотрим выполнение варианта 26. По данному заданию необходимо синтезировать автомат Мура с последовательностью изменения состояний в зависимости от значения входного сигнала zf:
z1: 1, 0, 2, 3,1;
z2: 0, 1, 3, 2, 0;
со следующими выходными сигналами:
w1 – состояние делится на 3;
w2 – нечетное состояние;
w3 – четное состояние.
12
Метод структурного синтеза – табличный; тип элементов памяти – Т-триггеры.
Выполнение контрольной работы
На этапе абстрактного синтеза построим отмеченную таблицу
переходов, которой полностью задается автомат Мура. По варианту
задания автомат Мура имеет четыре внутренних состояния: 0 → а0,
1 → а1,2 → а2, 3 → а3; два входных сигнала: z1и z2; три выходных
сигнала: w1, w2, w3.
Исходя из последовательности изменений внутренних состояний
автомата Мура в зависимости от значений входных сигналов zf под
действием сигнала z1 автомат из a0 переходит в a2, потом в a3, потом
в a1 и снова в a0. Под действием входного сигнала z2 автомат из a0
переходит в a1, потом в a3, потом в a2 и снова в a0.
Исходя из задания значений выходных сигналов:
w1 – соответствует a3;
w2 – соответствует a1;
w3 – соответствует a0 и a2.
Теперь, проанализировав задание к контрольной работе, построим
отмеченную таблицу переходов абстрактного автомата Мура (табл. 2).
Переходим к этапу структурного синтеза.
Определим количество элементов памяти – Т-триггеров:
R =]log2 (M + 1)[=]log2 (3 + 1)[= 2.
Таким образом, в структуре автомата Мура будут два Т-триггера:
ТА и ТВ.
Закодируем внутренние состояния автомата.
Таблица 2
Отмеченная таблица переходов абстрактного автомата Мура
wg
am
zf
w3
w2
w3
w1
a0
a1
a2
a3
z1
a2
a0
a3
a1
z2
a1
a3
a0
a2
Поскольку имеем два триггера, то разрядность кодовых комбинаций для внутренних состояний равна двум. Имеем:
à0 = 00 => ÀÂ;
13
à1 = 01 => ÀÂ;
à2 = 10 => ÀÂ;
à3 = 11 => ÀÂ.
Определим количество структурных входных каналов – разрядность кодовых комбинаций для входных сигналов:
L =]log2F[=]log2 2[= 1.
Закодируем входные сигналы:
z1 = 0 => x,
z2 = 1 => x.
Определим количество структурных выходных каналов – разрядность кодовых комбинаций для выходных сигналов:
N =]log2G[=]log2 3[= 2.
Закодируем выходные сигналы:
w1 = 01 => y1y2 ;
w2 = 10 => y1 y2 ;
w3 = 11 => y1y2 .
При кодировке параметров абстрактного автомата Мура исходили из совпадения индекса параметра с кодовым словом в двоичной
системе счисления, т. е.
à2 = 10 = ÀÂ; w3 = 11 = y1y2 .
Теперь можно построить закодированную отмеченную таблицу
переходов структурного автомата Мура (табл. 3).
Таблица 3
Закодированная отмеченная таблица
переходов структурного автомата Мура
yn
у1у2
y1 y2
у1у2
y1 y2
ÀÂ
ÀÂ
ÀÂ
АВ
x
ÀÂ
ÀÂ
АВ
ÀÂ
x
À Â
АВ
ÀÂ
ÀÂ
am
zl
14
Теперь определим сигналы возбуждения памяти, т. е. входные
сигналы для Т-триггеров ТА и ТВ. Для этого представим таблицу,
где определены сигналы возбуждения ТА и ТВ (табл. 5). Она строится на основании таблиц (3) и (4) – таблицы переходов Т-триггера.
Таблица 4
Q(t)
Q(t + 1)
T
0
0
0
0
1
1
1
0
1
1
1
0
Чтобы получить сигналы ТА и ТВ – входные сигналы триггеров А
и В, нужно вспомнить, что для изменения состояния Т-триггера на
его вход подается единичный сигнал (Ò = 1), а для сохранения предыдущего состояния подается нулевой сигнал (Ò = 0). Таким образом, для перехода из состояния à0 = AB в состояние à1 = ÀÂ на
вход триггера А подается Ò À = 0, так как состояние триггера А как
предыдущее, так и последующее не изменяется, оно нулевое ( A ) ; на
вход триггера В подается ÒÂ = 1, так как триггер В меняет свое состояние с нулевого на единичное (Â ® Â).
Теперь можно построить таблицу для сигналов возбуждения памяти (табл. 5).
Таблица 5
Отмеченная таблица сигналов возбуждения
структурного автомата Мура
yn
у1у2
y1 y2
у1у2
y1 y2
am
ÀÂ
ÀÂ
ÀÂ
АВ
zl
ТА
ТВ
ТА
ТВ
ТА
ТВ
ТА
ТВ
x
ТА
ÒÂ
ÒÀ
ТВ
ÒÀ
ТВ
ТА
ÒÂ
x
ÒÀ
ТВ
ТА
ÒÂ
ТА
ÒÂ
ÒÀ
ТВ
15
Из табл. 5 определим ТА и ТВ, которые описываются дизъюнкциями конъюнкций внутренних состояний и входных сигналов:
Ò À = ÀÂx Ú AÂx Ú ÀBõ ÚABx; (13)
ÒÂ =ABõ Ú AÂx Ú ÀBx Ú ÀÂõ. (14)
Из табл. 5 определим выходные сигналы у1 и у2, которые описываются дизъюнкциями внутренних состояний.
ó1 = AB Ú AÂ Ú ÀB=A Ú B ; (15)
ó2 = AB Ú ÀB Ú ÀB = À Ú B. (16)
Для построения структурной схемы автомата Мура переведем
выражения (13)–(16) в базис Пирса, используя законы де Моргана.
ТА= ÀÂx Ú AÂx Ú ÀBõ Ú ABx =
(
) (
)
= ( À Ú Â Ú õ) Ú ( À Ú Â Ú õ ) Ú À Ú Â Ú õ Ú À Ú Â Ú õ =
= РР(Р(А, В, х), Р (А, Â , õ ), Р (À, Â, õ) , Р (À, Â, õ)) ; (17)
ÒÂ = AÂõ Ú ÀÂx Ú ÀBx Ú ÀÂõ =
(
) (
) (
)
= ( À Ú Â Ú x ) Ú À Ú Â Ú õ Ú À Ú Â Ú õ Ú À Ú Â Ú õ = 16
= ÐÐ (Ð( À, Â, x ), Ð( À, Â, õ), Ð ( À, Â, õ), Ð ( À, Â, õ ));
(18)
x x
А
A
В
B
1
T TA
1
1
1
А
A
1
1
1
1
1
1
T TB В
B
В
1
1
1
1
1
y1
1
1
1
y2
Рис. 5. Структурная схема автомата Мура
ó1 = A Ú B = ÐÐ(A, B); (19)
ó2 = À Ú B = ÐÐ ( À, B). (20)
На основании выражений (17)–(20) строим структурную схему
автомата Мура (рис. 5).
2.3. Варианты задания для контрольной работы
Варианты заданий для контрольной работы представлены в
табл. 6; 7.
17
Таблица 6
Синтезировать автомат
Тип
автомата
Последовательность
изменения
состояний в
зависимости
от zf
z1 = 2, 0, 3, 1, 2...
z2 = 1, 3, 0, 2, 1...
МУРА
I
2
z1 = 2, 0, 3, 1, 2...
z2 = 1, 3, 0, 2, 1...
z1 = 2, 0, 3, 1, 2...
z2 = 1, 3, 0, 2, 1...
1
w1 – переход
из четного
состояния при
нечетном zf;
w2 – переход
из нечетного
состояния при
четном zf;
w3 – остальные
случаи
1
Выходные сигналы
1
МИЛИ
2
w1 – состояние ≥ 3;
w2 – четное
состояние;
w3 – нечетное
состояние
Метод
структурного
синтеза
Графический
Тип
элементов
памяти
R-S
3
w1 – состояние
делится на 3;
w2 – нечетное
состояние;
w3 – четное
состояние
2
II
3
w1 – переход
из четного
состояния при
четном zf;
w2 – переход
III
из нечетного
состояния при
нечетном zf;
w3 – остальные
случи
4
Табличный
1
IV
2
T
V
Таблица 7
Позиция
№ варинта
I
II
III
IV
V
1
2
3
4
5
6
7
8
9
10
1
2
1
2
1
1
1
1
1
2
3
2
1
3
2
1
2
3
1
2
4
2
1
2
4
4
4
1
4
3
2
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
18
Окончание табл. 7
Позиция
№ варинта
I
II
III
IV
V
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
1
2
1
2
1
2
1
2
1
2
1
2
2
1
1
2
3
1
2
3
1
2
3
1
2
3
1
1
2
2
3
3
1
3
1
3
4
3
4
3
1
3
4
2
2
1
1
3
1
1
2
1
3
2
2
1
2
2
1
1
2
1
1
2
1
2
1
1
2
1
1
2
1
2
1
2
1
2
1
2
Рекомендуемая литература
1. Мишура О. В. Цифровые автоматы. Основы алгебры логики. Минимизация логических функций при помощи диаграмм Вейча: метод. указ. для
студ. 2-го курса заочной формы обучения. СПб.: ГУАП, 2012.
2. Мишура О. В. Цифровые автоматы. Структурный синтез конечных
автоматов: учеб.-метод. пособие для студентов 1-го курса дневной формы
обучения. СПб.: ГУАП, 2014.
3. Пятибратов А. П., Кирпиченко А. А., Гудьно Л. П. Вычислительные
системы, сети и телекоммуникации. М.: Финансы и статистика, 2002.
4. Фрикс К. Вводный курс цифровой электроники. М.: Техносфера, 2004.
Содержание
1. Цели и задачи дисциплины, ее место в учебном процессе......... 2. Контрольная работа........................................................... 2.1. Формулировка задания к контрольной работе................. 2.2. Пример выполнения контрольной работы...................... 2.2.1. Структурный синтез автомата Мили.................... Выполнение контрольной работы................................. 2.2.2. Структурный синтез автомата Мура..................... 2.3. Варианты задания для контрольной работы.................... Рекомендуемая литература.................................................... 3
5
5
5
5
6
12
17
19
19
20
Документ
Категория
Без категории
Просмотров
1
Размер файла
842 Кб
Теги
mishyra2
1/--страниц
Пожаловаться на содержимое документа