Синтез комбинационных схем

Автор работы: Пользователь скрыл имя, 22 Января 2013 в 16:58, курсовая работа

Краткое описание

К упрощенной импликантной таблице (табл. 5) применим операцию удаления “лишних” столбцов (существенных вершин).
Таким образом из табл. 5 можно удалить столбец f, после чего получим табл. 6.
Дальнейшие упрощения табл. 6 невозможны. Для определения минимального покрытия можно использовать метод Петрика.

Скачать в ZIP архиве (92.67 Кб) Сколько стоит заказать работу?
Вложенные файлы: 1 файл

Дискретка (Автосохраненный).docx

— 131.50 Кб (Скачать файл)

Санкт-Петербургский национальный исследовательский университет 
информационных технологий, механики и оптики

 

 

 

Кафедра Информатики и прикладной математики

 

Курсовая работа по Дискретной математике по теме:

«Синтез комбинационных схем»

34 Вариант

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил:

Мячков Эдуард

Студент 1 курса

Группа 1121

2011-2012 уч. год

1)Составление таблицы  истинности

N

          

|-|

f

     0

00000

000

0

000

0

0

0

00001

010

2

000

0

2

1

00010

100

4

000

0

4

1

00011

110

6

000

0

6

0

00100

000

0

001

1

1

d

00101

010

2

001

1

1

d

00110

100

4

001

1

3

1

00111

110

6

001

1

5

0

01000

000

0

010

2

2

1

01001

010

2

010

2

0

0

01010

100

4

010

2

2

1

01011

110

6

010

2

4

1

01100

000

0

011

3

3

1

01101

010

2

011

3

1

d

01110

100

4

011

3

1

d

01111

110

6

011

3

3

1

10000

000

0

100

4

4

1

10001

010

2

100

4

2

1

10010

100

4

100

4

0

0

10011

110

6

100

4

2

1

10100

000

0

101

5

5

0

10101

010

2

101

5

3

1

10110

100

4

101

5

1

d

10111

110

6

101

5

1

d

11000

000

0

110

6

6

0

11001

010

2

110

6

4

1

11010

100

4

110

6

2

1

11011

110

6

110

6

0

0

11100

000

0

111

7

7

0

11101

010

2

111

7

5

0

11110

100

4

111

7

3

1

11111

110

6

111

7

1

D


 

2) Представление булевой  функции в аналитическом виде

КДНФ: \/\/\/\/\/\/

\/\/\/\/\/\/\/\/\/

ККНФ:

 

 

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

Нахождение простых  импликат (максимальных кубов).

     

=

Z(f)

1. 00001

2. 00010

3. 00100

4. 00101

5.00110

6. 01000

7.01010

8. 01011

9. 01100

10. 01101

11.  01110

12. 01111

13. 10000

14. 10001

15. 10011

16. 10101

17. 10110

18. 10111

19. 11001

20. 11010

21. 11110

22. 11111

 

1. 00X01   1-4

2. X0001   1-14

3. 00X10   2-5

4. 0X010   2-7

5.0010X    3-4

6. 001X0   3-5

7. 0X100   3-9

8. 0X101   4-10

9. X0101   4-16

10. 0X110   5-11

11. X0110   5-17

12. 010X0   6-7

13. 01X00   6-9

14. 0101X   7-8

15. 01X10   7-11

16. X1010   7-20

17. 01X11   8-12

18. 0110X   9- 10

19. 011X0   9-11

20. 011X1   10-12

21. 0111X   11-12

22. X1110   11-21

23. X1111   12-22

24. 1000X   13-14

25. 100X1   14-15

26. 10X01   14-16

27. 1X001   14-19

28. 10X11   15-18

29. 101X1   16-18

30. 1011X   17-18

31. 1X110   17-21

32.1X111    18-23

33. 11X10    20-21

34. 1111X    21-22

1. X0X01  1-26 2-9

2. 0XX10 3-15 4-10

3. 0X10X  5-18

4. 0X1X0  6-19 7-10

5. XX110  10-31 11-22

6. 01XX0  12-19 13-15

7.01X1X  14-21 15-17

8. X1X10 16-22

9. 011XX  18-21 19-20

10. X111X 21-34 22-23

11. 10XX1  25-29 26-28

12. 1X11X 31-32

=

0X101

1000X

1X001

1011X

11X10

X0X01

0XX10

0X10X

0X1X0

XX110

01XX0

01X1X

X1X10

011XX

X111X

10XX1

1X11X


 

 

 

 

 

 

 

 

Составление импликантной таблицы.

Таблица 4

Простые

Импликанты

(максимальные

кубы)

0-кубы

0

0

0

0

1

0

0

0

1

0

0

0

1

1

0

0

1

0

0

0

0

1

0

1

0

0

1

0

1

1

0

1

1

0

0

0

1

1

1

1

1

0

0

0

0

1

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

1

0

0

1

1

1

0

1

0

1

1

1

1

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1) 0X101

                              

2) 1000X

                

(*)

*

          

3) 1X001

                  

*

    

(*)

    

4) 1011X

                              

5) 11X10

                          

*

*

6) X0X01

                  

*

  

*

      

7) 0XX10

  

(*)

    

*

                    

8) 0X10X

            

*

                

9) 0X1X0

    

*

      

*

                

10) XX110

    

*

                      

*

11) 01XX0

      

(*)

*

  

*

                

12) 01X1X

        

*

(*)

  

*

              

13) X1X10

        

*

                

*

*

14) 011XX

            

*

*

              

15) X111X

              

*

            

*

16) 10XX1

                  

*

(*)

*

      

17) 1X11X

                            

*


 

Определение существенных импликант.

Существенные импликанты: 2,3,7,11,12,16.

Таблица 5

Простые

Импликанты

(максимальные

кубы)

0-кубы

0

0

1

1

0

0

1

0

1

0

0

1

1

0

0

0

1

1

1

1

1

0

0

0

1

1

0

1

0

1

1

1

0

1

0

1

1

1

1

0

a

b

c

d

e

f

g

h

 11X10

A

           

*

*

 X0X01

B

       

*

*

    

 0X10X

C

   

*

          

 0X1X0

D

*

  

*

          

 XX110

E

*

            

*

X1X10

F

 

*

        

*

*

011XX

G

   

*

*

        

 X111X

H

     

*

      

*

1X11X

I

             

*


 

Множество существенных импликант (максимальных кубов) образует ядро покрытия как его обязательную часть:

 

Определение минимального покрытия

Метод Петрика. Выпишем булево выражение Y, определяющее условие покрытия всех 0-кубов (существенных вершин), не покрываемых существенными импликантами, в соответствие с таблицей.

Y=(D\/E)(F)(C\/D\/G)(G\/H)(B)(B)(A\/F)(A\/E\/F\/H\/I)

Применим закон поглощения к  дизъюнктивным термам:

Y=FB(D\/E)(C\/D\/G)(G\/H)(A\/E\/F\/H\/I)  (2)

Выполняя операции попарного логического умножения применительно к термам, содержащим одинаковые буквы, с последующим применением закона поглощения, приведем исходную конъюнктивную форму Y (2) к дизъюнктивной

Y=FBDC\/FBEC\/FBD\/FBDG\/FBED\/FBEG(G\/H)(A\/E\/F\/H\/I)=FBDCG\/FBDCH\/FBECG\/

\/FBECH\/FBDG\/FBDH\/FBDG\/FBDGH\/FBEDG\/FBEDH\/FBEG\/FBEGH(A\/E\/F\/H\/I)=

=FBDCGA\/FBDCGE\/FBDCG\/FBDCGH\/FBDCGI\/ FBDCH\/ FBDCHE\/ FBDCH\/ FBDCH\/ \/FBDCHI\/ FBECGA\/ FBECGE\/ FBECGF\/ FBECGH\/ FBECGI\/ FBECHA\/ FBECH\/ FBECHF\/ FBECH\/ FBECHI\/ FBDGA\/ FBDGE\/ FBDG\/ FBDGH\/ FBDGI\/ FBDHA\/ FBDHE\/ FBDH\/ FBDH\/ FBDHI\/ FBDGHA\/ FBDGHE\/ FBDGH\/ FBDGHI\/ FBEDGA\/FBEDG\/FBEDGH\/FBEDGI\/ FBEDHA\/ FBEDH\/ FBEDHI\/ FBEGA\/ FBEG\/ FBEGH\/ FBEGI\/ FBEGHA\/ FBEGH\/ FBEGHI = FBDCGA\/FBDCGE\/FBDCG\/FBDCGH\/ FBDCH\/ FBDCHE\/ FBDCHI\/ FBECGA\/ FBECG\/ FBECGH\/ FBECGI\/ FBECHA\/ FBECH\/ FBECHI\/ FBDGA\/ FBDGE\/ FBDG\/ FBDGH\/ FBDGI\/ FBDHA\/ FBDHE\/ FBDH\/FBDHI\/ FBDGHA\/ FBDGHE \/ FBDGHI\/ FBEDGA\/FBEDG\/FBEDGH\/FBEDGI\/ FBEDHA\/ FBEDH\/ FBEDHI\/ FBEGA\/ FBEG\/ FBEGH\/ FBEGI\/ FBEGHA \/ FBEGHI = FBECH\/ FBDG\/ FBDH\/ FBEDH\/ FBEG

 

В полученном выражении каждый из восьми конъюнктивных термов соответствует  одному из вариантов покрытия, среди  которых находятся и минимальные

Возможны следующие варианты покрытия:

 

 

 

 

 

 

 

Дальнейшее упрощение  импликантной таблицы:

К упрощенной импликантной таблице (табл. 5) применим операцию удаления  “лишних”  столбцов  (существенных вершин).

Таким образом из табл. 5 можно удалить столбец f, после чего получим табл. 6.

Дальнейшие упрощения табл. 6 невозможны. Для определения минимального покрытия можно использовать метод Петрика.

 

 

 

 

 

 

 

 

Таблица 6

Простые

Импликанты

(максимальные

кубы)

0-кубы

0

0

1

1

0

0

1

0

1

0

0

1

1

0

0

0

1

1

1

1

1

0

0

0

1

1

1

0

1

0

1

1

1

1

0

a

b

c

d

e

g

h

 11X10

A

         

*

*

 X0X01

B

       

*

    

 0X10X

C

   

*

        

 0X1X0

D

*

  

*

        

 XX110

E

*

          

*

X1X10

F

 

*

      

*

*

011XX

G

   

*

*

      

 X111X

H

     

*

    

*

1X11X

I

           

*


 

 

4) Минимизация булевой функции на картах Карно

4.1 Определение МДНФ

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

X4X5                                      X4X5


   X2X3      00   01    11     10     X2X3     00     01    11    10

 

1

  

1

00

1

1

1

  

d

d

  

1

01

  

1

d

d

1

d

1

d

11

    

d

1

1

  

1

1

10

  

1

  

1


          X1: 0               X1: 1

 

МДНФ имеет следующий вид:

\/\/\/\/\/\/\/\/\/

\/

4.2 Определение МКНФ

 

X4X5                                      X4X5


   X2X3      00   01    11     10     X2X3     00     01    11    10

0

  

0

  

00

      

0

d

d

0

  

01

0

  

d

d

 

d

  

d

11

0

0

d

  
 

0

    

10

0

  

0

  

          X1: 0               X1: 1

  

МКНФ имеет следующий вид:

()()()

()()

()()()

5) Преобразование минимальных  форм булевой функции

Информация о работе Синтез комбинационных схем