Прикладная теория цифровых автоматов

Автор: Пользователь скрыл имя, 04 Марта 2013 в 13:55, курсовая работа

Описание работы

Потребность в вычислениях возникла у людей на самых ранних стадиях развития человеческого общества. Причем с самого начала для облегчения счета люди использовали различные приспособления. Многие из них были весьма интересными и остроумными по принципу действия, но все они обязательно требовали, чтобы в процессе вычислений активно участвовал человек-оператор. Качественно новый этап развития вычислительной техники наступил с изобретением и созданием электронных вычислительных машин, которые работают автоматически, без участия человека, в соответствии с заранее заданной программой.

Работа содержит 1 файл

1.doc

— 1.85 Мб (Скачать)

 

Минимальные ДНФ и их цена по Квайну имеет вид:

 

ТДНФ1

=

МДНФ1

ТДНФ2

=

МДНФ2

ТДНФ3

=

МДНФ3

ТДНФ4

=

МДНФ4

ТДНФ5

=

МДНФ5

ТДНФ6

=

МДНФ6

ТДНФ7

=

МДНФ7

ТДНФ8

=

МДНФ8

ТДНФ9

=

МДНФ9

ТДНФ10

=

МДНФ10

ТДНФ11

=

МДНФ11

ТДНФ12

=

МДНФ12


 

СМДНФ1  = СМДНФ2 = СМДНФ3 = СМДНФ4 = СМДНФ5 = СМДНФ6 = СМДНФ7 = СМДНФ8 = СМДНФ9 = СМДНФ10 = СМДНФ11 = СМДНФ12 = 2*2+3*3=11 

Найдем минимальную конъюнктивную  нормальную форму (МКНФ). Задана функция, принимающая значение «1» на y = Ù (2,3,9,11,13,22,25,26,27) и имеющая не определенное положение на у = х (0,7,14,15,16,17,28,29,30,31).

 

K0=

           

0

0

0

0

0

0

x

2

0

0

0

1

0

0

3

0

0

0

1

1

0

7

0

0

1

1

1

x

9

0

1

0

0

1

0

11

0

1

0

1

1

0

13

0

1

1

0

1

0

14

0

1

1

1

0

x

15

0

1

1

1

1

x

16

1

0

0

0

0

x

17

1

0

0

0

1

x

22

1

0

1

1

0

0

25

1

1

0

0

1

0

26

1

1

0

1

0

0

27

1

1

0

1

1

0

28

1

1

1

0

0

x

29

1

1

1

0

1

x

30

1

1

1

1

0

x

31

1

1

1

1

1

x


 

Находим сокращенную КНФ.

 

K'0=

 

K'1=

 

K'2=

 

K'3=

 

K'4=

Æ

~

00000

 

000x0

 

0xx11

 

x1xx1

   
 

00010

 

x0000

 

x1x01

       

~

10000

 

0001x

 

x10x1

       
 

00011

 

1000x

 

x1x11

       
 

01001

 

0x011

 

x11x1

       

~

10001

 

00x11

 

11xx1

       
 

01011

 

01x01

 

11x1x

       
 

01101

 

x1001

 

x111x

       
 

10110

 

1x001

 

111xx

       
 

11001

 

x1011

           
 

11010

 

x1101

           

~

00111

 

011x1

           

~

01110

 

1x110

           

~

11100

 

11x01

           
 

11011

 

110x1

           

~

01111

 

11x10

           

~

11101

 

1101x

           

~

11110

 

0x111

           

~

11111

 

x1110

           
     

0111x

           
     

1110x

           
     

111x0

           
     

11x11

           
     

x1111

           
     

111x1

           
     

1111x

           

Строим таблицу покрытия (см. таблица 5) и определяем ядро булевой функции.

Таблица 5

 

00010

00011

01001

01011

01101

10110

11001

11010

11011

 

x1xx1

   

~

~

~

 

~

 

~

A

0xx11

 

~

 

~

         

B

11xx1

           

~

 

~

C

11x1x

             

~

~

D

x111x

                 

E

111xx

                 

F

x1x01

   

~

 

~

 

~

   

G

x10x1

   

~

~

   

~

 

~

H

x1x11

     

~

       

~

I

x11x1

       

~

       

J

   

B

         

D

   

 

Строим сокращенную таблицу покрытия (см. таблица 6)

                                                                Таблица 6

 

00010

00011

10110

11010

 

0xx11

 

~

   

B

11x1x

     

~

D

   

B

 

D

 

 

Существует единственная экстремаль – х1хх1. Из сокращенной таблицы покрытий, включающей 3,4,5, 7, 9 столбцы и 1, 3, 4-9 строки, следует, что существует одно тупиковое покрытие:

 

ТКНФ1

=

x1xx1

   

0xx11

   

11x1x


 

Минимальные КНФ и их цена по Квайну имеет вид:

 

 

ТКНФ1

 

 

 

 

=

 

 


 

СМКНФ1 = 2*1+3*2=8

Табличный метод минимизации (карты  Карно)

Карты Карно - это специальным образом организованные таблицы соответствия: столбцы и строки таблицы соответствуют всевозможным наборам не более двух переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных. Благодаря этому соседние по вертикали и горизонтали клетки отличаются только одной переменной. Клетки, расположенные симметрично по краям таблицы также считаются соседними и отличаются одной переменной.

Для ДНФ  клетки наборов, на которых функция принимает значение «1» заполняются «1». Нулевые клетки не заполняются. Для КНФ клетки наборов, на которых функция принимает значение «0» заполняются «0». Единичные клетки не заполняются.

Аналогично n-мерному кубу, совокупности двух соседних клеток соответствует 1-куб, 4-х соседних клеток - 2-куб т.д.

Считывание  минтермов осуществляется по следующему правилу: клетки, образующие S-куб дают минтерм (n-s)-го ранга, в который входят те (n-s) переменных, которые сохраняют одинаковые значения на этом s-кубе. Для ДНФ значению «1» соответствуют прямые значения переменных, значению «0» - их отрицания. Для КНФ значению «0» соответствуют прямые значения переменных, значению «1» - их отрицания. Переменные, не сохраняющие свои значения на s-кубе, в минтерм (макстерм для КНФ) не входят.

Задача минимизации с помощью  карт Карно формулируется аналогично задаче минимизации на n-мерном кубе. Данный алгоритм минимизации дает МДНФ для значений функции «1» или  МКНФ для значений функции «0».

Использование карт Карно требует более простых построений (наглядных), особенно в случае функций от 4-х переменных, в сравнении с отображением на n-мерном кубе. Для отображения функций 5-ти переменных используются две карты Карно от 4-х переменных, для функций 6-ти переменных используются четыре карты Карно:

При n³5 наглядность карт Карно теряется. Карты Закревского позволяют сохранить наглядность табличного метода при n£8.

Получим МДНФ булевой функции методом  карт Карно. Заполняем карты Карно для заданной функции из пяти переменных, что отображают значения Х5 (таблицы 7 и 8).

 

                                                      Таблица 7                                                            Таблица 8                         

Исходя  из карт Карно получаем:

 

Получим МКНФ булевой функции методом  карт Карно. Заполняем карты Карно для заданной функции из пяти переменных, что отображают значения Х5 (таблицы 9 и 10).

                                           Таблица 9                                                           Таблица 10                         

Исходя из карт Карно получаем:

 

Реализация  функции согласно с  базисом ИЛИ-НЕ, оценка затрат, построение функциональной схемы и анализ ее работы методом p-алгаритма.

Для реализации выбираем  МДНФ и подаем ее в заданном элементном базисе ИЛИ-НЕ.

 

 

Для реализации  этой  функции  по  приведенному  выражению необходимо   использовать   один   логических  элемент  2И,  два логический элемента 3И, один   логических  элемент  4И, один  логический элемент 4ИЛИ-НЕ.

Представлению функции    в    виде    ДНФ    соответствует двухуровневая КС (если считать,  что на ее вход могут  поступать как  прямые так и  инверсные входные сигналы),  на первом уровне которой элементы И ,  а их выходы объединяются на втором уровне элементом   ИЛИ   .   Такое   построение   КС  обеспечивает  ее максимальное быстродействие,  так  как  ранг  схемы  минимален.  Однако,  не  всегда возможно на первом уровне и,  особенно,  на втором выбрать логические элементы с требуемым ,  т.к. может оказаться, что ЛЭ с таким не выпускаются промышленностью. В этом случае необходимо с помощью нескольких элементов с меньшим получить    эквивалент   с   большим либо,   что предпочтительней,  преобразовать БФ, перейдя от ДНФ к скобочной форме.  Этот  переход сопровождается уменьшением логических элементов,  требуемого для построения схемы.  Осуществить такой переход можно с помощью факторного алгоритма, суть которого рассмотрим на примере.

Выбранную булева функция в виде:

 

С помощью факторного алгоритма получим скобочную  форму для заданной функции. Для  этого обозначим все конъюнкции буквами:

 

 

и будем  рассматривать  их  как  некоторые  множества.  Находим попарное пересечения множеств:

          

 

Полученные пересечения  показывают  общие  части  отдельных  конъюнкций.  Выбираем  пересечение,  которое  имеет  наибольшую длину (если такое отсутствует,  то выбирают  то,  которое  чаще всего встречается).  В данном случае это   . Поэтому из конъюнкций А и В и С выносим общую часть . Тогда имеем:

Информация о работе Прикладная теория цифровых автоматов