Другие предметы \ Проектирование цифровых устройств

Умножитель по модулю 9. Оптимизация, страница 4

№

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

134

1345

*

-

2

136

1356

*

-

3

146

1246

*

-

4

346

2346

*

-

Получаем .

2.  Оптимизация

Так как функция содержит элементарные конъюнкции только четвертого ранга, ее оптимизация возможна за счет элементарных конъюнкций третьего и меньших рангов. Рассмотрим элементарные конъюнкции третьего ранга:

№

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

124

1234

*

-

2

126

1256

*

-

3

134

1234

*

-

4

135

135

*

-

5

136

136

*

-

6

145

1245

*

-

7

146

1456

*

-

8

156

1256

*

-

9

234

1234

*

-

10

236

2356

*

-

11

246

246

*

-

12

345

2345

*

-

13

346

346

*

-

14

356

2356

*

-

Следовательно, оптимизация  невозможна. Получаем .

3.  Оптимизация

Так как функция содержит элементарные конъюнкции только четвертого и третьего ранга, то ее оптимизация возможна за счет элементарных конъюнкций третьего и меньшего ранга. Рассмотрим элементарные конъюнкции третьего ранга:

№

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

123

1236

*

-

2

135

-

1

+

3

136

1346

*

-

4

246

-

1

+

5

346

1346

*

-

6

456

3456

*

-

Рассмотрим элементарные конъюнкции второго ранга:

№

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

13

134

*

-

2

15

125

*

-

3

24

124

*

-

4

26

126

*

-

5

35

235

*

-

6

46

146

*

-

Построим таблицу покрытия:

1

3

5

2

4

6

1

2

3

4

1

2

4

5

1

2

5

6

1

4

5

6

2

3

4

5

2

3

5

6

135

246

Конъюнкции 135 и 246 существенны. Включаем их в окончательное решение. Получаем .

4.  Оптимизация

Так как функция содержит элементарные конъюнкции третьего и второго ранга, то ее оптимизация возможна за счет элементарных конъюнкций второго и меньшего ранга. Рассмотрим конъюнкции второго ранга:

№

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

15

-

1

+

2

24

-

2

+

Элементарные конъюнкции первого ранга покрывают нулевое подмножество , следовательно, оптимизация ими невозможна.

Построим таблицу покрытия:

Скачать файл