Исследование методов анализа и синтеза логических схем

МОСКОВСКИЙ  АВИАЦИОННЫЙ ИНСТИТУТ

(государственный  технический университет)

филиал  «Восход» 

Кафедра ВТ

                                             «УТВЕРЖДАЮ»

                   Преподаватель Слепова А.Ш.

                                                ___________«___»_______ 200__г.

                                                     подпись 
 
 

КУРСОВАЯ  РАБОТА

на тему: «Исследование методов анализа  и синтеза логических схем»

  
 
 

по дисциплине: Математическая логика и теория алгоритмов 
 
 

Студента  гр. ДВМ3-61   ____________ /Жумадилдаев К.Р./ 

«___»_____________ 200__г. 
 
 
 
 

Байконур 2009 г. 

 

Содержание 

Введение 4

1 Расчетная часть 5

Задание №1 5

Задание №2 6

Задание №3 7

Задание №4 11

Задание №5 13

Задание №6 16

Задание №7 18

Задание №8 20

Задание №9 21

2 Метод факторизации 25

2.1 Теоретическая часть 25

2.2 Описание алгоритма программы 25

2.3 Кодирование программы 26

2.4 Анализ полученных результатов 27

Заключение 29

Список литературы 30

Приложение А 31

Приложение Б 32

Приложение В 35 

 

     Введение

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

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

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

 

1 Расчетная часть 

Задание №1

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

Таблица 1 – Таблица истинности

Переменные

X1X2X3X4

 Значения функции  F
0000 0
0001 1
0010 1
0011 1
0100 1
0101 0
0110 0
0111 0
1000 1
1001 0
1010 1
1011 0
1100 1
1101 0
1110 1
1111 0
 

Решение. 
 

Рисунок 1 – Логическая схема функции 

Задание №2

Преобразовать функцию, заданную в ДНФ в СДНФ и СКНФ 
 

Решение. 

СДНФ: 
 
 
 
 
 

 

Таблица 2 – Таблица  истинности

Переменные

X1X2X3X4

 Значения функции  F
0000 1
0001 0
0010 1
0011 0
0100 0
0101 1
0110 0
0111 0
1000 1
1001 0
1010 1
1011 1
1100 1
1101 1
1110 1
1111 0
 

СКНФ: 
 
 
 

Задание №3

Минимизировать  заданную функцию :

а) по методу Квайна

б) по методу Квайна-Мак-Класски

в) по метод минимизирующих карт 
 
 

 

а) Минимизация  методом Квайна 
 
 
 

Производятся  всевозможные склеивания минтермов, входящих в СДНФ; выполняется операция поглощения над минтермами каждого ранга, при этом: 

 (1 - 2) 

(2 - 4)

(2 - 6) 

(3 - 4) 

(3 - 8) 

(5 - 6) 

(5 - 8) 

 

Оставшийся непоглощенный минтерм: . 

МДНФ: 
 
 

б) Минимизация методом Квайна-Мак-Класски 
 
 

 

Таблица 3 – Таблица  истинности

m         F
0 0 0 0 0 0
1 0 0 0 1 1
2 0 0 1 0 0
3 0 0 1 1 1
4 0 1 0 0 0
5 0 1 0 1 0
6 0 1 1 0 1
7 0 1 1 1 1
8 1 0 0 0 0
9 1 0 0 1 0
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 0
13 1 1 0 1 1
14 1 1 1 0 1
15 1 1 1 1 0
 

Составляются  группы:

1 – группа 0001
2 – группа 0011, 0110, 1010
3 – группа 0111, 1011, 1101, 1110
 

Выполняется сравнение  соседних групп и производится операция склеивания:

1 – группа 00-1
2 – группа 0-11, -011, 011-, -110, 101-, 1-10

Минтерм «1101» не склеивается, соответственно, он будет включен в итоговую МДНФ. 

МДНФ: 
 
 

 

в) Минимизация  методом минимизирующих карт 
 
 

Исходная функция  наносится на карту Карно: 

 

Рисунок 2 – Минимизирующая карта Карно  

Выбираются комбинации, которые объединены наибольшим числом «1» и при этом накрывают все  «1» карты, и производится склейка:

; ; ; ; ; ; ;  

МДНФ: 
 
 
 
 
 
 

Далее находится  тупиковая ДНФ методом карт Карно: 

Рисунок 3 – Минимизирующая карта Карно  

Выбираются комбинации, которые объединены наибольшим числом «1» и при этом накрывают все  «1» карты, и производится склейка:

; ; ; ;  

ТДНФ: 
 

Задание №4

Найти МКНФ функции : 
 

 

Решение. 

Находится СДНФ для составления таблицы истинности. 

СДНФ: 
 
 
 

По полученной СДНФ строится таблица истинности, где находится обратная функция  F-1. 

Таблица 4 – Таблица  истинности для заданной и обратной от нее функции

Переменные

X1X2X3X4

 Значения функции  F Значения функции  F-1
0000 0 1
0001 0 1
0010 1 0
0011 1 0
0100 1 0
0101 0 1
0110 1 0
0111 1 0
1000 0 1
1001 0 1
1010 1 0
1011 1 0
1100 1 0
1101 0 1
1110 0 1
1111 0 1
 

Полученная обратная функция наносится на карту Карно: 

 

Рисунок 4 – Минимизирующая карта Карно  

Выбираются комбинации, которые объединены наибольшим числом «1» и при этом накрывают все  «1» карты, и производится склейка: 
 

МДНФ обратной функции: 
 

Далее находится  МКНФ путем инвертирования МДНФ обратной функции. 

МКНФ: 
 
 

Задание №5

Минимизировать  не полностью определенную функцию. Синтезировать логическую схему. 

Для заданной функции  строится таблица истинности. 

Таблица 5 – Таблица  истинности для заданной функции  F

m         F
0 0 0 0 0 0
1 0 0 0 1 -
2 0 0 1 0 0
3 0 0 1 1 1
4 0 1 0 0 -
5 0 1 0 1 1
6 0 1 1 0 0
7 0 1 1 1 0
8 1 0 0 0 -
9 1 0 0 1 1
10 1 0 1 0 1
11 1 0 1 1 -
12 1 1 0 0 0
13 1 1 0 1 1
14 1 1 1 0 0
15 1 1 1 1 0
 

Полученная функция наносится на карту Карно, причем предполагается, что при запрещенном наборе функция F будет равна «1»: 

 

Рисунок 4 – Минимизирующая карта Карно

Выбираются комбинации, которые объединены наибольшим числом «1» и при этом накрывают все  «1» карты, и производится склейка:

; ;;

 

МДНФ: 
 

Строится импликантная матрица: 

Таблица 6 – Импликантная матрица

           
  X   X    
    X X   X
      X X  
    X      
 

МДНФ: 
 

 

Рисунок 5 – Логическая схема функции

 

Задание №6

Записать СДНФ для функции  в базисах Пирса и Шеффера: 
 
 
 

Решение. 
 
 
 

Базис Пирса: 

Применяя закон Де Моргана, получаем следующую функцию: 
 
 
 
 

Применяя закон  двойного отрицания и закон «0» и «1», получаем следующую функцию: 
 
 
 
 
 

 

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

Базис Шеффера: 

Применяя закон  двойного отрицания и Де Моргана, получаем следующую функцию: 
 
 
 

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

 

Задание №7

Минимизировать  функцию  в базисе Шеффера: 
 

Синтезировать логическую схему. 

Решение. 

Перед тем, как  представить минимизированную функцию  в базисе Шеффера, необходимо минимизировать исходную СДНФ. Данная функция была ранее минимизирована в задании  №3. 

МДНФ: 
 
 
 
 
 
 

Базис Шеффера: 

Применяя закон  двойного отрицания и Де Моргана, получаем следующую функцию: 
 
 
 

 

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

Рисунок 6 – Логическая схема функции в базисе Шеффера

Задание №8

Минимизировать  функцию  в базисе Пирса: 
 

Синтезировать логическую схему. 

Решение. 

Перед тем, как  представить минимизированную функцию  в базисе Пирса, необходимо найти  МКНФ. Для исходной функции МКНФ была найдена в задании №4. 

МКНФ: 
 

Базис Пирса: 

Применяя закон  двойного отрицания и Де Моргана, получаем следующую функцию: 
 

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

Рисунок 7 – Логическая схема функции в базисе Пирса 

Задание №9

Синтезировать логическую схему неполного дешифратора, выделяющего следующие наборы:

y0, y1, y4, y6, y11, y12, y14, y15 

Решение. 

Перед тем, как  составить таблицу истинности и  синтезировать логическую схему, определяется количество входных сигналов: 
 
 

 

Таблица 7 – Таблица  истинности полного дешифратора

x3 x2 x1 x0 y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 

Согласно заданию, в таблице истинности полного  дешифратора выделяются заданные наборы. Исходя из этого, составляется таблица  истинности неполного дешифратора. 

 

Таблица 8 – Таблица  истинности неполного дешифратора

x3 x2 x1 x0 y0 y1 y4 y6 y11 y12 y14 y15
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 1 0 0 0
1 1 0 0 0 0 0 0 0 1 0 0
1 1 0 1 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 1 0
1 1 1 1 0 0 0 0 0 0 0 1

Исследование методов анализа и синтеза логических схем 📙 Курсовая → 🆔 96073

Исследование методов анализа и синтеза логических схем 📙 Курсовая → 🆔 96073

Исследование методов анализа и синтеза логических схем