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

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

Страницы работы

12 страниц (Word-файл)

Скачать файл

Содержание работы

Оптимизация функции .

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

Рассмотрим нулевое подмножество функции . Оно содержит следующие конъюнкции: 12346 и 13456. Очевидно, что конъюнкция меньшего ранга, которая не будет покрывать нулевое подмножество функции, - 25. Получаем .

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

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

№	Конъюнкция	Покрываемый набор из	Количество покрываемых импликант	Множество импликант
1	1245	-	0	-
2	1256	-	0	-
3	2345	-	0	-
4	2356	-	0	-
5	2456	-	0	-

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

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

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

№	Конъюнкция	Покрываемый набор из	Количество покрываемых импликант	Множество импликант
1	12	-	2	+
2	13	-	1	+
3	14	-	2	+
4	16	-	1	+
5	23	-	1	+
6	25	-	2	+
7	26	-	1	+
8	34	-	1	+
9	35	-	1	+
10	36	-	0	-
11	45	-	2	+
12	46	-	1	+
13	56	-	1	+

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

№	Конъюнкция	Покрываемый набор из	Количество покрываемых импликант	Множество импликант
1	1	15	*	-
2	2	24	*	-
3	3	-	2	+
4	4	24	*	-
5	5	15	*	-
6	6	-	2	+

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

	1 2 4	1 2 5	1 3 5	1 4 5	1 5 6	2 3 4	2 4 5	2 4 6
3
6
12
14
25
45

Конъюнкции 3 и 6 существенны. Включаем их в окончательное решение. Сокращаем таблицу покрытия.

	1 2 4	1 2 5	1 4 5	2 4 5
12					A
14					B
25					C
45					D

Получаем две минимальных ДНФ, любая из которых может быть выбрана в качестве оптимальной. Произвольно выбираем . Получаем .

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

Так как функция содержит только конъюнкции второго ранга, то ее оптимизация возможна конъюнкциями первого ранга. Но оптимизация невозможна, так как конъюнкции первого ранга входят в нулевое подмножество функции. Получаем .

Оптимизация функции .

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

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

№	Конъюнкция	Покрываемый набор из	Количество покрываемых импликант	Множество импликант
1	12345	-	1	+
2	12346	-	1	+
3	12456	-	1	+
4	13456	-	1	+

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

№	Конъюнкция	Покрываемый набор из	Количество покрываемых импликант	Множество импликант
1	1235	12356	*	-
2	1236	12356	*	-
3	1346	-	1	+
4	1456	1456	*	-
5	2346	23456	*	-
6	2456	23456	*	-
7	3456	23456	*	-