Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


јналитический метод минимизации ‘јЋ




( вайна-ћак- ласски)

 

¬ основу данного метода положен закон склеивани€ конституэнт единицы —ƒЌ‘. ¬ результате склеивани€ конституэнт единицы получаетс€ сокращенна€ ƒЌ‘. —окращенной ƒЌ‘ называетс€ така€ ƒЌ‘ заданной функции, котора€ может содержать лишние слагаемые.

 

ѕример 3.1. Ќайти сокращенную ƒЌ‘ следующего логического выражени€ заданного в —ƒЌ‘

 

 онституэнты единицы —ƒЌ‘ представл€ют собой наборы аргументов, записанные в виде букв. ≈сли аргумент равен нулю, то буква, соответствующа€ ему, имеет знак отрицани€.

јлгоритм получени€ сокращенной ƒЌ‘ следующий:

1.  ажда€ конституэнта единицы, заданного логического выражени€ представл€етс€ двоичным числом.

2. ѕолученные двоичные числа разбиваютс€ на группы по числу единиц и записываютс€ в первый столбец в пор€дке возрастани€ числа единиц в группе.

3. ѕроизводитс€ склеивание двоичных чисел первой группы с двоичными числами второй группы, двоичные числа второй группы с двоичными числами третей группы и т.д. —клеиватьс€ будут только соседние двоичные числа. ƒва двоичных числа называютс€ соседними, если они отличаютс€ между собой только в одном разр€де, например 110 и 100.

¬ результате склеивани€ получаетс€ сокращенное двоичное число (импликанта), где вместо аргумента, которым отличались два двоичных числа, ставитс€ черточка. —окращенные двоичные числа записываютс€ во второй столбец и также дел€тс€ на группы по числу единиц. —клеенные двоичные числа первого столбца отмечаютс€ выбранным знаком. ќдно и то же число может склеиватьс€ несколько раз, но отмечаетс€ только один раз.

—окращенные двоичные числа второго столбца аналогично могут склеиватьс€ между собой. ¬ результате получаютс€ сокращенные двоичные числа с двум€ черточками и записываютс€ в третий столбец и т.д.

ƒл€ склеивани€ двоичных чисел второго и последующих столбцов необходимо выполнение двух условий:

1. „тобы склеиваемые числа были соседними.

2. „ерточки в склеиваемых числах должны сто€ть в одинаковых разр€дах.

—клеивание импликант (сокращенных двоичных чисел) продолжаетс€ до тех пор, пока выполн€ютс€ эти два услови€.

4. ѕосле прекращени€ процесса склеивани€ все сокращенные и не сокращенные двоичные числа всех столбцов, которые не отмечены знаком склеивани€, рекомендуетс€ обозначить латинскими буквами, сумма этих букв будет представл€ть собой сокращенную ƒЌ‘. ѕовторно встречающиес€ импликанты не рассматриваютс€.

ѕримечание. ¬ процессе склеивани€ рекомендуетс€ каждое двоичное число первого столбца обозначить его дес€тичным эквивалентом. Ёто необходимо дл€ удобства при получении тупиковых ƒЌ‘.

 


–ешение примера 3.1. ¬ыполн€€ вышеизложенный алгоритм получим:

ѕервый столбец ¬торой столбец “ретий столбец
0. 0 0 0 0 Ú 0, 1 0 0 0 - Ú 0, 1, 2, 3 0 0 - - A
1. 0 0 0 1 Ú 0, 2 0 0 - 0 Ú 0, 1, 8, 9 - 0 0 - B
2. 0 0 1 0 Ú 0, 4 0 - 0 0 Ú 0, 2, 4, 6 0 - - 0 C
4. 0 1 0 0 Ú 0, 8 - 0 0 0 Ú 0, 4, 2, 6 0 - - 0  
8. 1 0 0 0 Ú 1, 3 0 0 - 1 Ú 0, 8, 1, 9 - 0 0 -  
3. 0 0 1 1 Ú 1, 9 - 0 0 1 Ú 1, 3, 9, 11 - 0 - 1 D
6. 0 1 1 0 Ú 2, 3 0 0 1 - Ú 1, 9, 3, 11 - 0 - 1  
9. 1 0 0 1 Ú 2, 6 0 - 1 0 Ú 2, 3, 6, 7 0 - 1 - E
7. 0 1 1 1 Ú 4, 6 0 1 - 0 Ú 2, 6, 3, 7 0 - 1 -  
11. 1 0 1 1 Ú 8, 9 1 0 0 - Ú 3, 7, 11, 15 - - 1 1 F
15. 1 1 1 1 Ú 3, 7 0 - 1 1 Ú 3, 11, 7, 15 - - 1 1  
      3, 11 - 0 1 1 Ú      
      6, 7 0 1 1 - Ú      
      9, 11 1 0 - 1 Ú      
      7, 15 - 1 1 1 Ú      
      11, 15 1 - 1 1 Ú      

»з результатов склеивани€ видно, что все числа первого и второго столбцов склеились. Ќе склеились только числа третьего столбца, из которых выбираем импликанты A, B, C, D, E, F, повтор€ющиес€ отбрасываем. “аким образом, сокращенна€ ƒЌ‘ будет иметь вид

A Ú B Ú C Ú D Ú E Ú F = .

 

¬се слагаемые сокращенной ƒЌ‘ называютс€ простыми импликантами. »з сокращенной ƒЌ‘ можно получить тупиковые ƒЌ‘, если они будут иметь место. “упиковой ƒЌ‘ называетс€ така€ ƒЌ‘ ни одно слагаемое, из которой исключить нельз€, не измен€€ ее значение.

ƒл€ получени€ тупиковых ƒЌ‘ необходимо построить импликантную таблицу, котора€ состоит из вертикальных и горизонтальных линий. „исло вертикальных линий равно числу конституэнт единицы, которые содержатьс€ в —ƒЌ‘ заданного логического выражени€. „исло горизонтальных линий равно числу простых импликант сокращенной ƒЌ‘. ¬ рассмотренном примере 3.1. число конституэнт единицы равно 11 (0, 1, 2, 4, 8, 3, 6, 9, 7, 11, 15), а число простых импликант сокращенной ƒЌ‘ равно 6 (A, B, C, D, E, F). »мпликантна€ таблица будет следующа€

“аблица 3.1.

»мпликантна€ таблица дл€ примера 3.2

                         
                         
                         
                         
                         
                         
                         
                         

 

ѕростые импликанты получились в результате склеивани€ конституэнт единицы столбца 1. Ќапример проста€ импликанта ј получилась в результате склеивани€ четырех конституэнт единицы 0, 1, 2, 3 (см. столбец 3). ¬ таблице 3.1. на пересечении горизонтальной линии импликанты ј с вертикальными лини€ми конституэнт единицы 0, 1, 2, 3 сто€т крестики, свидетельствующие о том, что импликанта ј поглощает конституенты единицы 0, 1, 2, 3. ¬се остальные крестики в таблице 3.1. на пересечени€х вертикальных и горизонтальных линий говор€т о поглощении простыми импликантами соответствующих конституэнт единицы.

ƒл€ получени€ тупиковых ƒЌ‘ из таблицы 3.1. запишем следующее выражение

y = (A Ú B Ú C)(A Ú B Ú D)(A Ú C Ú E)C×B×(A Ú D Ú E Ú F)(C Ú E)(B Ú D)(E Ú

Ú F) × (D Ú F)F (3.1)

¬ыражение (3.1) представл€ет собой произведение сумм простых импликант, которые поглощают конституэнты единицы —ƒЌ‘. ƒл€ получени€ всех тупиковых ƒЌ‘ необходимо в выражении (3.1) раскрыть скобки. ¬ результате получим сумму произведений простых импликант.  аждое полученное произведение по составу простых импликант будет представл€ть собой тупиковую ƒЌ‘.

–аскрытие скобок выражени€ (3.1) представл€ет собой достаточно сложную процедуру, поэтому получить тупиковые ƒЌ‘ можно простым анализом импликантной таблицы и выражени€ (3.1). ¬ выражении (3.1) в качестве отдельных сомножителей присутствуют импликанты B, C, F, которые об€зательно должны войти в тупиковую ƒЌ‘, т.к. конституэнта 4 (см. табл. 3.1.) поглощаетс€ только импликантой —, конституэнта 8 только импликантой ¬, а конституэнта 15 только импликантой F. ¬о все суммы простых импликант выражени€ (3.1) в качестве слагаемого входит хот€ бы одна из импликант B, C, F. —ледовательно, все конституэнты единицы будут поглощатьс€ импликантами B, C, F. ќтсюда следует, что тупикова€ ƒЌ‘ дл€ заданной ‘јЋ в примере 3.2. будет только одна

B Ú C Ú F= .

Ёта тупикова€ ƒЌ‘ одновременно будет и минимальной ƒЌ‘.

 

ѕример 3.2. Ќайти минимальную ƒЌ‘ следующего логического выражени€

.

–ешение

ѕервый столбец ¬торой столбец
0. 0 0 0 0 Ú 0, 2 0 0 - 0 A
2. 0 0 1 0 Ú 0, 8 - 0 0 0 B
8. 1 0 0 0 Ú 2, 6 0 - 1 0 C
6. 0 1 1 0 Ú 8, 9 1 0 0 - D
9. 1 0 0 1 Ú 6, 7 0 1 1 - E
7. 0 1 1 1 Ú 9, 13 1 - 0 1 F
13. 1 1 0 1 Ú 7, 15 - 1 1 1 G
15. 1 1 1 1 Ú 13, 15 1 1 - 1 H

 

ѕроизошло склеивание только соседних двоичных чисел первого столбца. —окращенные двоичные числа второго столбца не склеиваютс€ между собой. —ледовательно, все они будут импликантами сокращенной ƒЌ‘. ѕолучили сокращенную ƒЌ‘ в следующем виде

A Ú B Ú C Ú D Ú E Ú F Ú G Ú H =00-0 Ú -000 Ú 0-10 Ú 100- Ú

Ú 011- Ú 1-01 Ú -111 Ú 11-1 =

.

ƒл€ получени€ тупиковых ƒЌ‘ строитс€ импликантна€ таблица

“аблица 3.2.

                   
                   
                   
                   
                   
                   
                   
                   
                   
                   

 

Ќа основе импликантной таблицы 3.2., по аналогии с примером 3.1, запишем выражение

y = (A Ú B)(A Ú —)(¬ Ú D)(— Ú E)(D Ú F)(E Ú G)(F Ú H)(G Ú H).

–аскрыв скобки данного выражени€ получим

y = ABDEH Ú ABEFG Ú ABEFH Ú ACDEH Ú ACDFG Ú ADEH Ú ADGH Ú

Ú ADEFG Ú ADEFH Ú BCDEH Ú BCDGH Ú BCFG Ú BCEFH.

¬се полученные произведени€ по составу импликант €вл€ютс€ тупиковыми ƒЌ‘. »з полученных тупиковых ƒЌ‘ необходимо выбрать минимальную ƒЌ‘. “ак как все импликанты A B C D E F G H по длине одинаковые, то минимальной ƒЌ‘ будет та тупикова€ ƒЌ‘, котора€ содержит наименьшее число импликант. “аких тупиковых ƒЌ‘ три ADEH, ADGH и BCFH, которые состо€т из четырех импликант. Ћюба€ из этих трех тупиковых будет минимальной.

Ќапример B Ú C Ú F Ú H = -000 Ú 0-10 Ú 1-01 Ú 11-1 =

= .

 






ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 792 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

80% успеха - это по€витьс€ в нужном месте в нужное врем€. © ¬уди јллен
==> читать все изречени€...

2062 - | 1935 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.026 с.