close

Вход

Забыли?

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

?

Mishura 0CFA238117

код для вставкиСкачать
Министерство образования и науки российской федерации
Федеральное государственное автономное образовательное
учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ЦИФРОВЫЕ АВТОМАТЫ.
МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ
ПРИ ПОМОЩИ ДИАГРАММ ВЕЙЧА
Методические указания
к выполнению контрольной работы
Санкт-Петербург
2013
Составитель О. В. Мишура, кандидат технических наук, доцент
Рецензент В. П. Попов, кандидат технических наук, доцент
Приведены программа и методические указания к выполнению
контрольной работы по одному из разделов дисциплины «Цифровые
автоматы», связанной с минимизацией логической функции при помощи диаграмм Вейча.
Предназначены для студентов заочной формы обучения по направлению 230400, квалификация – бакалавр.
Подготовлены кафедрой информационно-сетевых технологий (№ 53)
и рекомендованы к изданию редакционно-издательским советом
Санкт-Петербургского государственного университета аэрокосмического приборостроения.
Редактор Г. Д. Бакастова
Компьютерная верстка Н. Н. Караваевой
Сдано в набор 05.04.15. Подписано к печати 21.06.13. Формат 60×84 1/16.
Бумага офсетная.Уч.-изд. л. 0,7. Усл. печ. л. 0,9. Тираж 100 экз. Заказ № 339.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2013
1. Цели и задачи дисциплины,
ее место в учебном процессе
Программа дисциплины «Цифровые автоматы» составлена в соответствии с Федеральным государственным образовательным
стандартом высшего профессионального образования по направлению 230400 «Информационные системы и технологии», профили:
– 230403 – Информационные технологии в дизайне,
– 230404 – Информационные технологии в медиа индустрии,
– 230406 – Информационные технологии в бизнесе.
Квалификация – бакалавр.
Программа включает следующие разделы:
1. Машинная арифметика.
2. Аналитическое представление функций алгебры логики.
3. Введение в теорию автоматов.
4. Введение в теорию графов.
Целью преподавания дисциплины «Цифровые автоматы» является ознакомление с классическими математическими моделями
систем обработки дискретных сигналов.
В области воспитания личности в рамках подготовки по данной
дисциплине является формирование основ общекультурных и профессиональных компетенций для приобретения качеств, необходимых создателю новых приборов и технологий, таких как целеустремленность, организованность, трудолюбие, ответственность,
гражданственность, коммуникативность и др.
Для реализации целей изучения дисциплины необходимо выполнение следующих задач:
– ознакомление студентов с основами машинной арифметики;
– ознакомление студентов с основами алгебры логики, аналитического представления функций алгебры логики; минимизацией
логических функций;
– ознакомление студентов с теорией графов и ее практическим
использованием;
3
– представление о современном состоянии научных проблем по
организации цифровых автоматов;
– навыки работы с технической литературой.
По окончании изучения дисциплины студент должен знать основы машинной арифметики, алгебру логики, основы теории графов,
типы триггеров; уметь использовать машинные коды, функции алгебры логики, диаграммы Вейча – Карно, универсальные базисы;
иметь навыки минимизации логических выражений.
В соответствии с учебным планом общая трудоемкость дисциплины, изучаемой в 3-м семестре студентами заочной формы обучения, квалификация — бакалавр, составляет 108 часов, из них лекции – 6 часов, практические занятия – 6 часов, самостоятельная
работа – 81 час. Студентам заочной формы обучения читаются установочные лекции. Предусмотрено выполнение одной контрольной
работы. Полное изучение дисциплины студенты-заочники осуществляют самостоятельно. Вид итогового контроля – экзамен.
Практические занятия включают решение конкретных задач,
связанных с тематикой основных разделов изучаемой дисциплины.
Примерный перечень тем практических занятий:
– представление чисел в ЦВМ с фиксированной и плавающей запятой;
– машинные коды;
– выполнение арифметических операций для чисел с фиксированной и плавающей запятой в машинных кодах;
– свойства логических переменных и логических функций;
– представление логических функций в совершенных нормальных и нормальных конъюнктивных и дизъюнктивных формах;
– применение диаграмм Вейча – Карно для минимизации логических функций;
– введение в теорию графов.
Основной формой изучения материала является самостоятельная работа студентов-заочников с технической литературой.
4
2. Контрольная работа
В течение семестра каждый студент-заочник должен выполнить
одну контрольную работу. По результатам ее выполнения проверяется качество усвоения студентами той части лекционного материала, которая связана с тематикой второго и третьего разделов изучаемой дисциплины, т. е. с аналитическим представлением функций алгебры логики, минимизацией функций алгебры логики при
помощи диаграмм Вейча, представлением логических функций после минимизации в базисах Шеффера и Пирса, построением логических схем.
Выполнять контрольную работу следует только после того, как
проработана соответствующая литература.
2.1. Формулировка задания к контрольной работе
Контрольная работа имеет название: «Минимизация логической функции при помощи диаграмм Вейча» и включает следующие пункты, которые должны быть выполнены в процессе решения
конрольной работы:
1) представить таблицу истинности для функции, зависящей от
четырех переменных;
2) записать в таблице истинности выражения в СДНФ и СКНФ
для реализуемой функции;
3) минимизировать функцию, представленную в СДНФ и СКНФ,
по единицам и нулям при помощи диаграммы Вейча;
4) представить минимизированную функцию в ДНФ и КНФ;
5) подсчитать сумму рангов для функции в ДНФ и КНФ;
6) реализовать функцию, представленную в форме с минимальной суммой рангов, в базисе Шеффера и Пирса;
7) построить логические схемы для реализуемой функции в базисах Шеффера и Пирса, используя парафазный код подачи переменных, от которых зависит функция.
2.2. Пример выполнения контрольной работы
Пусть логическая функция, зависящая от четырех переменных
А, B, C и D, задана при помощи таблицы истинности (табл. 1).
Чтобы представить значение функции в СДНФ, необходимо выделить наборы переменных, на которых функция равна единице, поставить в соответствие этому набору конъюнкцию соответствующих
5
Таблица 1
А
В
С
D
f
CДНФ
0
0
0
0
1
ABCD
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
СКНФ
A ∨ B ∨ C ∨D
AB CD
A ∨ B ∨C ∨D
A ∨B ∨ C ∨D
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
–
1
0
0
0
–
1
0
0
1
1
1
0
1
0
–
1
0
1
1
1
1
1
0
0
–
1
1
0
1
0
A ∨B ∨ C ∨D
1
1
1
0
0
A ∨B ∨C ∨ D
1
1
1
1
1
A BC D
A ∨B ∨C ∨ D
ABC D
AB C D
ABCD
переменных, а потом полученные конъюнкции соединить знаками
дизъюнкции. Поэтому имеем:
f(A,B,C,D) = ABCD ∨ AB CD ∨ A BC D ∨
∨ ABC D ∨ AB C D∨ A B C D,
(1)
Сумма рангов полученного выражения R = 24.
Чтобы представить значение функции в СКНФ, необходимо выделить наборы переменных, на которых функция принимает нулевые значения, поставить в соответствие этому набору дизъюнкцию
соответствующих переменных, а потом полученные дизъюнкции
соединить знаками конъюнкции. Поэтому имеем:
f(A,B,C,D) = (A ∨ B ∨ C ∨D)(A ∨ B ∨C ∨D)(A ∨B ∨ C ∨D)
(A ∨B ∨C ∨ D)(A ∨B ∨ C ∨D)(A ∨B ∨C ∨ D) ,
(2)
Сумма рангов полученного выражения R = 24.
Для минимизации заданной функции представим диаграмму
Вейча, расставим в ней единичные значения функции, а также в со6
ответствующих клетках диаграммы – прочерки. Пустые клетки будут соответствовать нулевым значениям функции.
В заполненной диаграмме Вейча необходимо найти соседние области. При нахождении соседних областей необходимо помнить,
что количество областей должно быть минимальным, а количество
клеток в каждой соседней области – максимальным, но кратно 2n.
При минимизации по единицам области на рис. 1 представлены
сплошной линией. Каждой соседней области нужно поставить в соответствие конъюнкцию, в которой отсутствуют переменные, изменяющие в этой области свое значение. При получении соседних областей используются клетки с прочерками, которые увеличивают
площадь соседних областей. Полученные конъюнкции объединяются знаками дизъюнкции. Получаем выражение функции в ДНФ:
f(A,B,C,D) =BD ∨ AB ∨ A B D ∨ B C D,
(3)
Сумма рангов полученного выражения R = 10.
При минимизации по нулям области на рис. 1 представлены штриховыми линями. Каждой соседней области нужно поставить в соответствие дизъюнкцию, в которой отсутствуют переменные, изменяющие в этой области свое значение. При получении соседних областей
используются клетки с прочерками, которые увеличивают площадь
соседних областей. Полученные дизъюнкции объединяются знаками конъюнкции. Получаем выражение функции в КНФ:
f(A,B,C,D) = (B ∨ D) (A ∨B ∨C)(A ∨B ∨D)(A ∨B ∨C ∨ D).
(4)
Сумма рангов полученного выражения R = 8.
А
1
–
1
–
–
1
1
1
D
1
–
C
Рис. 1
7
Переведем оба выражения (3) и (4) в базисы Шеффера и Пирса.
При переводе в базис Шеффера воспользуемся законами де Моргана:
x Ú y = xy.
Таким образом, двойное отрицание возьмем для всего выражения, т. е. поставим его над знаками дизъюнкции, от которых нужно
избавиться:
f ( A, B, C, D) = B D Ú AB Ú ABD Ú BCD = B D Ú AB Ú ABD Ú BCD =
(
)
= S S ( B, D ), S ( A, B), S ( A, B, D ), S ( B, C, D ) . (5)
построим логическую схему (рис. 2). Поскольку в выражении
присутствуют как прямые, так и инверсные переменные, можно
воспользоваться парафазным кодом подачи переменных.
При переводе ДНФ в базис Пирса воспользуемся законами де
Моргана:
xy = x Úy.
Таким образом, двойное отрицание возьмем от элементарных
конъюнкций в ДНФ, т. е. поставим его над знаками конъюнкций,
от которых нужно избавиться:
f ( A, B, C, D ) = B D Ú AB Ú ABD Ú BCD =
(
) (
) (
) (
)
= B Ú D Ú A Ú B Ú A Ú B Ú D Ú B Ú C Ú D =;
–
–
–
–
AABBCCDD
&
[
&
[
&
[
&
[
Рис. 2
8
&
[
f (A,B,C,D)
чтобы получить выражение в базисе Пирса, необходимо поставить
двойное отрицание над знаками дизъюнкций, т. е.
) (
(
) (
) (
)
= BÚD Ú AÚB Ú AÚBÚD Ú BÚCÚD =
(
)
= PP P ( B, D ), P ( A, B), P ( A, B, D ), P ( B, C, D ) .
(6)
построим логическую схему (рис. 3). Поскольку в выражении (6)
имеются инверсные переменные, воспользуемся парафазным кодом
подачи переменных.
переведем в базисы Шеффера и Пирса выражение функции
в КНФ (4). При переводе КНФ в базис Шеффера двойное отрицание
возьмем от отдельных дизъюнкций, т. е.
f ( A, B, C, D) = ( B Ú D )( A Ú B Ú C)( A Ú B Ú D) =( ÂD )( ABC )( ABD ) =;
для получения выражения в базисе Шеффера нужно добавить двойное
отрицание над знаками конъюнкций, объединяющих термы, т. е.
(
))
(
= ( ÂD )( ABC )( ABD ) = SS S ( B, D ), S ( A, B, C ), S A,B, D .
–
–
–
–
AABBCCDD
1
1
1
1
f(A,B,C,D)
1
1
Рис. 3
9
–
–
–
–
AABBCCDD
&
[
&
[
&
&
&
f(A,B,C,D)
[
[
[
Рис. 4
–
–
–
–
AABBCCDD
1
[
1
[
1
1
[
Рис. 5
10
f(A,B,C,D)
Затем представим логическую схему (рис. 4). Поскольку в выражении (7) присутствуют инверсные переменные, воспользуемся парафазным кодом подачи переменных.
Чтобы получить выражение в базисе Пирса от КНФ, необходимо
поставить двойное отрицание над знаками конъюнкции, которые
отсутствуют в базисе Пирса, т. е.
f ( A, B, C, D ) = ( B Ú D )( A Ú B Ú C )( A Ú B Ú D ) =
= (B Ú D) Ú ( A Ú B Ú C) Ú ( A Ú B Ú D) =
(
(8)
)
= P P ( B, D ), P ( A, B,C ), P ( A, B, D ) .
построим логическую схему (рис. 5). Поскольку в выражении (8)
имеются инверсные переменные, воспользуемся парафазным кодом
подачи переменных.
2.3. Содержание отчета по контрольной работе
1. Таблица истинности для функции, зависящей от четырех переменных. Данные для таблицы истинности берутся из таблицы вариантов заданий для контрольной работы (п. 2.4).
2. Выражения функции в СДНФ и СКНФ.
3. Диаграмма Вейча, построенная по таблице истинности.
4. Выражения функции в ДНФ и КНФ, полученные по диаграмме Вейча при минимизации функции по единицам и по нулям.
5. Перевод ДНФ и КНФ в базисы Шеффера и Пирса.
6. Логические схемы в базисах Шеффера и Пирса для парафазного кода подачи переменных.
2.4. Варианты заданий для контрольной работы
Варианты заданий представлены в табл. 2.
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Таблица 2
1
0
0
1
–
–
1
0
0
1
0
–
1
–
–
1
0
2
0
1
–
0
1
–
–
1
0
–
1
0
0
1
0
0
3
1
0
–
1
–
1
–
1
0
1
–
0
1
–
1
0
4
1
–
1
0
1
–
1
–
–
1
0
–
1
–
0
0
11
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
5
–
1
1
0
–
0
1
1
0
–
–
1
1
0
–
0
6
0
–
1
1
–
0
0
–
1
–
0
1
1
–
0
0
7
–
0
1
1
0
0
1
0
0
1
–
0
1
–
0
1
8
1
0
–
1
0
1
0
1
–
1
0
0
–
–
1
1
9
0
1
–
0
1
1
1
–
0
–
0
1
1
1
–
0
10
–
0
1
1
0
–
0
1
1
1
1
0
–
0
1
1
11
1
0
–
1
0
0
–
–
–
0
0
1
–
–
1
0
12
0
1
0
–
1
0
1
1
1
0
–
–
0
1
1
1
13
0
–
1
–
0
1
0
–
1
–
0
1
0
1
0
0
14
–
0
–
1
0
–
1
0
–
0
1
1
1
0
–
0
15
0
1
–
0
–
–
0
1
1
1
0
–
0
1
1
0
16
0
0
–
0
1
–
–
1
1
0
0
–
0
1
1
0
17
–
0
–
0
–
1
1
0
0
1
1
–
1
1
0
0
18
0
–
0
–
1
1
1
1
0
1
1
0
–
0
–
0
19
–
0
1
–
0
0
0
1
–
–
1
0
–
0
1
1
20
0
0
–
1
1
1
1
0
–
0
–
0
1
1
0
0
21
1
–
–
–
1
0
–
–
1
0
0
1
0
–
–
1
22
0
0
0
–
0
–
1
1
0
1
–
–
1
–
1
0
23
0
1
0
0
1
–
–
1
–
–
0
1
–
1
0
–
24
1
–
–
–
0
–
1
1
1
0
–
–
1
0
–
1
0000
0001
окончание табл. 2
12
Библиографический список
1. Мишура О. В. Цифровые автоматы. Основы алгебры логики.
Минимизация логических функций при помощи диаграмм Вейча: метод. указ. для студентов 2-го курса заочной формы обучения,
СПб.: ГУАП, 2012.
2. Пятибратов А. П., Кирпиченко А. А., Гудьно Л. П. Вычислительные системы, сети и телекоммуникации. М.: Финансы и статистика, 2002.
3. Фрикс К. Вводный курс цифровой электроники. М.: Техносфера, 2004.
13
Содержание
1. Цели и задачи дисциплины, ее место в учебном
процессе..................................................................... 3
2. Контрольная работа.................................................. 5
2.1. Формулировка задания к контрольной работе........ 5
2.2. Пример выполнения контрольной работы.............. 5
2.3. Содержание отчета по контрольной работе............. 11
2.4. Варианты заданий для контрольной работы .......... 11
Библиографический список........................................... 13
14
Для заметок
15
Документ
Категория
Без категории
Просмотров
0
Размер файла
751 Кб
Теги
0cfa238117, mishura
1/--страниц
Пожаловаться на содержимое документа