Основы теории конечных динамических систем

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

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

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

Кафедра: ИТИиУ 

«Утверждаю»

Преподаватель ___________ Мирошникова Е.Н.

«        »                       2009 г. 
 
 
 
 

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

По дисциплине: О.Т.К.Д.С. 
 
 
 
 

Студент гр. ДА 2-44                         Корсаков А.А.

«        »                       2009 г. 
 
 
 
 
 

  г. Байконур 2009 год 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Содержание

Введение           

1  Расчет первой функции         

    1.1 Минимизация  исходной функции с помощью  метода  
    элементарных преобразований       

    1.2 Минимизация  функции с помощью карты Карно    

    1.3 Нахождение  минимальных покрытий      

    1.4 Нахождение  цены по Квайну       

    1.5 Нахождение нулевого покрытия функции и МКНФ    

    1.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски       

    1.7 Минимизация исходной функции с применением метода метод Петрика

    1.8 Построение  комбинационной схемы с однофазными  входами  

    1.9 Факторное  преобразование и построение  схемы с однофазными 
    входами и двухвходовыми элементами     

    1.10 Сравнение  двух схем по задержке и  цене по Квайну   

2 Расчет второй  функции         

    2.1 Минимизация  исходной функции с помощью  метода  
    элементарных преобразований       

    2.2 Минимизация  функции с помощью карты Карно    

    2.3 Нахождение минимальных покрытий      

    2.4 Нахождение  цены по Квайну       

    2.5 Нахождение нулевого покрытия функции и МКНФ    

    2.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски        

    2.7 Минимизация исходной функции с применением метода  Петрика 

    2.8 Построение комбинационной схемы с однофазными входами  

    2.9 Факторное преобразование и построение схемы с однофазными 
    входами и двухвходовыми элементами     

    2.10 Сравнение двух схем по задержке и цене по Квайну   

3 Расчет третьей функции         

    3.1 Минимизация исходной функции с помощью метода  
    элементарных преобразований       

    3.2 Минимизация функции с помощью карты Карно    

    3.3 Нахождение минимальных покрытий      

    3.4 Нахождение цены по Квайну       

    3.5 Нахождение нулевого покрытия функции и МКНФ    

    3.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски        

    3.7 Минимизация исходной функции с применением метода Петрика 

    3.8 Построение комбинационной схемы с однофазными входами  

    3.9 Факторное преобразование и построение схемы с однофазными 
    входами и двухвходовыми элементами     

    3.10 Сравнение двух схем по задержке и цене по Квайну   

4 Расчет четвертой функции        

    4.1 Минимизация исходной функции с помощью метода  
    элементарных преобразований       

    4.2 Минимизация функции с помощью карты Карно    

    4.3 Нахождение минимальных покрытий      

    4.4 Нахождение цены по Квайну       

    4.5 Нахождение нулевого покрытия функции и МКНФ    

    4.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски       

    4.7 Минимизация исходной функции с применением метода Петрика 

    4.8 Построение комбинационной схемы с однофазными входами  

    4.9 Факторное преобразование и построение схемы с однофазными 
    входами и двухвходовыми элементами     

    4.10 Сравнение двух схем по задержке и цене по Квайну    

Заключение           

Список используемой литературы       

Приложение А          

Приложение Б           

 

    Введение

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

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

 

    1 Расчет  первой функции

    

    1.1 Минимизация исходной функции с помощью метода элементарных преобразований

    1.2 Минимизация функции с помощью карты Карно

 

     Рисунок 1.1 – Карта Карно для ДНФ

  

 

 
 
 

    1.3 Нахождение минимальных покрытий

 1 0000 +  
1 000X (1-2) m        
2 0001 +   2 0X10 (3-5) m   XX01 m (6-8)
3 0010 +   3 01X1 (4-6) m   XX01   (9-11)
4 0101 +   4 10X1 (7-9) m        
5 0110 +   5 X010 (3-8) m  
000X    
6 0111 +   6 1X01 (7-10) +   0X10    
7 1001 +   7 00X0 (1-3) m   01X1    
8 1010 +   8 0X01 (2-4) +   10X1    
9 1011 +   9 X001 (2-7) +   X010    
  10 1101    +     10 X101 (4-10) +   00X0    
          11 011X (5-6) m   011X    
          12 101X (8-9) m   101X    
                  XX01    

    1.4 Нахождение цены по Квайну

    1.5 Нулевое покрытие функции и МКНФ

Рисунок 1.2 – Карта Карно для КНФ 

- МКНФ 

 1 0011 m  
1 X100 (2-4) m       X100
2 0100 +     2 11X0 (4-5) m   11X0
3 1000 +   3 111X (5-6) m   111X
4 1100 +   4 1X00 (3-4) m   1X00
5 1110 +           0011
6 1111 +              

    1.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски

    По  данным пункта 1.3 составляем таблицу 1.1

Таблица 1.1

    0000 0001 0010 0101 0110 0111 1001 1010 1011 1101
A 000X + +                
B 0X10     +   +          
C 01X1       +   +        
D 10X1             +   +  
E X010     +         +    
F 00X0 +   +              
G 011X         + +        
H 101X               + +  
I XX01   +   +     +     +

                                   

  

    1.7 Минимизация исходной функции с применением метода Петрика

    По  данным таблицы 1.1 находятся минимальные  покрытия:

 

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

                        

                                

    1.8 Построение комбинационной схемы с однофазными входами

 

Рисунок 1.3 – Комбинационная схема с однофазными входами

    1.9 Факторное преобразование и построение схемы с однофазными входами и двухвходовыми элементами

 

Рисунок 1.4 – Комбинационная схема с однофазными входами и двухвходовыми элементами 

    1.10 Сравнение двух схем по задержке и цене по Квайну

 

 

    После факторизации задержка и цена по Квайну увеличились.

 

    2 Расчет второй  функции

    

    2.1 Минимизация исходной функции с помощью метода элементарных преобразований

    2.2 Минимизация функции с помощью карты Карно

Рисунок 2.1 – Карта Карно для ДНФ 

 
 
 
 

    2.3 Нахождение минимальных покрытий

 1 0000 +  
1 00X0 (1-2) m           
2 0010 +   2 001X (2-3) m     X1X1 m (5-10)
3 0011 +   3 X010 (2-7) m  
X1X1   (6-7)
4 0101 +   4 0X11 (3-5) m            
5 0111 +   5 01X1 (4-5) +    
 
    

   

  

 

 00X0    
6 1001 +   6 X101 (4-9) +   001X    
7 1010 +   7 X111 (5-10) +   X010    
8 1100 +   8 1X01 (6-9) m   0X11    
  9 1101 +     9 110X (8-9) m   1X01    
  10 1111 +     10 11X1 (9-10) +   110X    
                  X1X1    
                         

    2.4 Нахождение цены по Квайну

    2.5 Нулевое покрытие функции и МКНФ

Рисунок 2.2 – Карта Карно для КНФ 
 
 

- МКНФ 

 1 0001 m  
1 01X0 (2-3) m     0001
2 0100 +     2 X110 (4-5) m 1000
3 0110 +     3 X110 (3-6) m 1011
4 1000 m         01X0
5 1011 m           X110
6 1110 +            
 

    2.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски

    По  данным пункта 2.3 составляем таблицу 2.1 

Таблица 2.1

    0000 0010 0011 0101 0111 1001 1010 1100 1101 1111
A 00X0 + +                
B 001X   + +              
C X010   +         +      
D 0X11     +   +          
E 1X01           +     +  
F 110X               + +  
G X1X1       + +       + +

                                                                                    

     

    2.7 Минимизация исходной функции с применением метода Петрика

    По  данным таблицы 2.1 находятся минимальные  покрытия:

                                  

    2.8 Построение комбинационной схемы с однофазными входами

 

Рисунок 2.3 – Комбинационная схема с однофазными входами

    2.9 Факторное преобразование и построение схемы с однофазными входами и двухвходовыми элементами

Рисунок 2.4 – Комбинационная схема с однофазными входами и двухвходовыми элементами

    2.10 Сравнение двух схем по задержке и цене по Квайну

 

 

    После факторизации задержка и цена по Квайну увеличились.

    3 Расчет  третьей функции

    

    3.1 Минимизация исходной функции с помощью метода элементарных преобразований

    3.2 Минимизация функции с помощью карты Карно

Рисунок 3.1 – Карта Карно для ДНФ 

 
 
 
 

    3.3 Нахождение минимальных покрытий

 1 0001 +
1 X001 (1-6) +  
X0X1 (1-6)
2 0010 + 2 00X1 (1-3) +   X0X1 (2-10)
3 0011 + 3 001X (2-3) +   0X1X (3-7)
4 0110 + 4 0X10 (2-4) +   0X1X (4-5)
5 0111 + 5 0X11 (3-5) +   XX11 (5-11)
6 1001 + 6 X011 (3-7) +   XX11 (6-9)
7 1011 + 7 011X (4-5) +   X11X (7-13)
8 1100 + 8 X110 (4-9) +   X11X (8-9)
9 1110 + 9 X111 (5-10) +        
10 1111 + 10 10X1 (6-7) +  
11X0  
        11 1X11 (7-10) +   X0X1  
        12 11X0 (8-9) m   0X1X  
        13 111X (9-10) +   XX11  
                    X11X  
 

      3.4 Нахождение цены по Квайну

    3.5 Нулевое покрытие функции и МКНФ

Рисунок 3.2 – Карта Карно для КНФ

- МКНФ 

 1 0000 +  
1 0X00 (1-2) m  
0X00
2 0100 +   2 X000 (1-4) m   X000
3 0101 +   3 010X (2-3) m   010X
4 1000 +   4 X101 (3-6) m   X101
5 1010 +   5 10X0 (4-5) m   10X0
6 1101 +            

    3.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски

    По  данным пункта 3.3 составляем таблицу 3.1

    Таблица 3.1

    0001 0010 0011 0110 0111 1001 1011 1100 1110 1111
A 11X0               + +  
B X0X1 +   +     + +      
C 0X1X   + + + +          
D XX11     +   +   +     +
E X11X       + +       + +
   
     
 
   
 

   

    3.7 Минимизация исходной функции с применением метода Петрика

    По  данным таблицы 3.1 находятся минимальные  покрытия:

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

     

    3.8 Построение комбинационной схемы с однофазными входами

 

Рисунок 3.3 – Комбинационная схема с однофазными входами 

    3.9 Факторное преобразование и построение схемы с однофазными входами и двухвходовыми элементами

Рисунок 3.4 – Комбинационная схема с однофазными входами и двухвходовыми элементами 

    3.10 Сравнение двух схем по задержке и цене по Квайну

 

 

После факторизации задержка и цена по Квайну увеличились.

 

    4 Расчет четвертой  функции

    

    4.1 Минимизация исходной функции с помощью метода элементарных преобразований

    4.2 Минимизация функции с помощью карты Карно

Рисунок 4.1 – Карта Карно для ДНФ 

    4.3 Нахождение минимальных покрытий

 1 000 +  
1 0Y0 (1-2) m  
0Y0    
2 010 +   2 Y00 (1-4) m   Y00    
3 011 +   3 01Y (2-3) m   01Y    
4 100 +   4 10Y (4-5) m   10Y    
5 101 +                    
 
 
 

    4.4 Нахождение цены по Квайну

    4.5 Нулевое покрытие функции и МКНФ

Рисунок 4.2 – Карта Карно для КНФ 
 

- МКНФ

 1 000 + m
1 11Y (2-3) m  
000    
2 110 +               11Y    
3 111 +                    

    4.6 Минимизация исходной функции с применением метода Квайне-Мак-Класски

    По  данным пункта 4.3 составляем таблицу 4.1

    Таблица 4.1

        000 010 011 100 101
    A 0Y0 + +      
    B Y00 +     +  
    C 01Y   + +    
    D 10Y       + +

                                         

    

    4.7 Минимизация исходной функции с применением метода Петрика

Основы теории конечных динамических систем 📙 Курсовая → 🆔 163463

Основы теории конечных динамических систем 📙 Курсовая → 🆔 163463

Основы теории конечных динамических систем