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

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

1

2

3

4

1

2

4

6

1

3

4

5

1

3

4

6

1

4

5

6

1

2

3

5

6

2

3

4

5

6

1235

1236

2456

3456

Выбираем конъюнкции 1235 и 2456. Получаем .

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

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

№

Конъюнкция

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

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

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

1

123

1236

*

-

2

124

-

1

+

3

126

1236

*

-

4

134

-

1

+

5

145

-

1

+

6

146

-

1

+

7

235

-

2

+

8

256

-

2

+

9

345

3456

*

-

10

456

3456

*

-

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

№

Конъюнкция

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

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

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

1

12

125

*

-

2

13

135

*

-

3

15

125

*

-

4

16

136

*

-

5

23

234

*

-

6

24

234

*

-

7

25

125

*

-

8

26

1236

*

-

9

34

234

*

-

10

35

135

*

-

11

45

245

*

-

12

46

246

*

-

13

56

156

*

-

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

1

2

4

1

3

4

1

4

5

1

4

6

1

2

5

6

1

3

5

6

2

3

4

5

2

3

4

6

2

3

5

6

124

134

145

146

235

256

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

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

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

№

Конъюнкция

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

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

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

1

15

-

3

+

2

24

-

3

+

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

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

1

4

3

6

1

2

5

1

3

5

1

5

6

2

3

4

2

4

5

2

4

6

15

24

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

Скачать файл