Курсовая работа: Синтез и анализ логической схемы при кубическом задании булевой функции

X110100

0ZZZZY1

X11X100

0ZZZZYZ

XX11100

0000110 0100101 Æ 10000X0 0X11111 Æ

ZZZZYZZ

1011010

- ¹Æ ¹Æ ¹Æ ¹Æ Æ ¹Æ ¹Æ Æ ¹Æ Æ

Полученное минимальное покрытие:

1X1XX11

XX1X1X0

00X0XX0

0X00101

X0X00X0

XX1111X

101XX1X

Cтоимость полученного покрытия равна 36 ( стоимость исходного покрытия равна 53 ).

2. ПОСТРОЕНИЕ ФАКТОРИЗОВАННОГО ПОКРЫТИЯ

Покрытие, полученное на основе простых импликант и выделения из них L-экстремалей, принято называть минимальным. Однако практика показывает, что дополнительная минимизация возможна при помощи факторизации. Таким образом, минимальным следует считать факторизованное покрытие, а не множество L-экстремалей.

Факторизация покрытия основана на операции m-произведения, которая предназначена для выделения общей части двух кубов. Эта операция является поразрядной:

0 при a_i = b_i = 0, i = 1,n;

a_i mb_i = 1 при a_i = b_i = 1, i = 1,n;

m во всех остальных случаях.

Символ m указывает координату исходных кубов, которая различна в них, либо есть Х.

Куб, в котором хотя бы одна координата является m, называется m-кубом и обозначается через е_m . Такой куб может участвовать в m-произведении, тогда при умножении на координату m должна получаться координата m.

Стоимость для m-куба определяется путем подсчета числа координат со значениями 0 и 1. Куб с наибольшей стоимостью считается максимальным. Если стоимость равна 0, то m-куб считается пустым, он равен Æ. Покрытие с учетом m-куба записывается в несколько измененном виде: под m-кубом фиксируются соответствующие ему кубы с сохранением тех координат, которые расположены под символами m.

Алгоритм факторизации покрытия является циклическим. Количество циклов равно числу уровней разложения покрытия ( числу m-кубов ). В разложенном по многим уровням покрытии выделяются на i-м цикле m-куб е_m ⁱ , M_i ( множество кубов с прочерками, соответствующее е_m ⁱ ), C_i (множество кубов, которые будут рассматриваться на ( i+1)-м цикле).

Алгоритм факторизации можно сформулировать следующим образом:

1. Вычисляются m-произведения всех пар из С_{i -1} . В первом цикле С₀ = Е. Во втором цикле дело надо иметь с С₁ , в третьем – с С₂ и т.д.

2. Выбирается m-куб с наибольшей стоимостью е_m ⁱ . Если несколько кубов имеют одинаковую стоимость, то выбирается первый.