Факторизация покрытий

В основе первого алгоритма факторизации (μ-алгоритм) лежит μ-произведение, которое обозначается a_μb, слагается из результатов покоординатных произведений

и выполняется в соответствии с таблицей 1:

Таблица 1.

Таким образом, μ-произведение двух координат равно нулю, если обе координаты равны нулю, равно единице, если обе координаты равны единице и равно μ во всех остальных случаях.

1. Берем полученное минимизированное покрытие C₀(F):

2. Определяют μ-произведения всех кубов из C₀(F). Это удобнее проделать при помощи следующей таблицы (Табл.1.2). По вертикали в первой слева колонке размещены кубы покрытия C₀(F), по горизонтали в первой сверху строчке размещены те же кубы, без последнего. На месте пересечения кубов самих с собой ставят прочерки.

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

Таблица 2 - μ-произведения всех кубов из C₀(F)

	1X1X1	001XX	X11X0	0101X	0000X
1X1X1	-	-	-	-	-
001XX	µ µ1 µ µ	-	-	-	-
X11X0	µ µ1 µ µ	µ µ1 µ µ	-	-	-
0101X	µ µ µ µ µ	0 µ µ µ µ	µ1 µ µ µ	-	-
0000X	µ µ µ µ µ	00 µ µ µ	µ µ µ µ µ	0 µ0 µ µ	-
0X010	µ µ µ µ µ	0 µ µ µ µ	µ µ µ µ0	0 µ01 µ	0 µ0 µ µ

3. Выбираем маскирующий куб C_μ , имеющий максимальную стоимость. Стоимость куба определяется по формуле:

где r_μ– общее число координат куба, не равных μ.

Кубом, имеющим максимальную стоимость, будет куб

4. В таблице отмечаем кубы, отмаскированные выбранным маскирующим кубом. Ими будут кубы 0X010, 0101X .

5. Покрытие C₀(F) разбиваем на три части. Вверху располагают кубы, кубы, которые не покрываются маскирующим кубом. Затем записывается маскирующий куб. Под ним помещаются отмаскированные кубы с прочерками на тех координатах, которые не равны μ в маскирующем кубе.

6. Отмаскированные кубы исключаем из рассмотрения. После исключения отмаскированных кубов алгоритм повторяется.

7. Вновь строится таблица (Таблица 3)

Таблица 3 - μ-произведения всех кубов из C₁(F)

	1X1X1	001XX	X11X0	0000X
1X1X1	-	-	-	-
001XX	µ µ1 µ µ	-	-	-
X11X0	µ µ1 µ µ	µ µ1 µ µ	-	-
0000X	µ µ µ µ µ	00 µ µ µ	µ µ µ µ µ	-
0 µ01 µ	µ µ µ µ µ	0 µ µ µ µ	µ µ µ µ µ	0 µ0 µ µ

8. Выбирается маскирующий куб максимальной стоимости.

Выберем один из кубов, им будет куб

9. Отмечаются кубы, отмаскированные C_μ3. В данном случае таковыми будут 0000Х, 0 µ01 µ .

10. Покрытие C₂(F) разбивается вновь на три части.

11. Снова строим таблицу

Таблица 4 - μ-произведения всех кубов из C₂(F)

	1X1X1	001XX	X11X0
1X1X1	-	-	-
001XX	µ µ1 µ µ	-	-
X11X0	µ µ1 µ µ	µ µ1 µ µ	-
0 µ0 µ µ	µ µ µ µ µ	0 µ µ µ µ	µ µ µ µ µ

Выбираем маскирующие кубы с максимальной стоимостью.

Отмечаем кубы, отмаскированные C_μ5. В данном случае таковыми будут 001ХХ, Х11Х0, 1Х1Х1. И строим покрытие.

12. Так остались еще неотмаскированные кубы, снова строим таблицу.

Таблица 5 - μ-произведения всех кубов из C₃(F)

	0 µ0 µ µ
0 µ0 µ µ	-
µ µ 1 µ µ	µ µ µ µ µ

13. Алгоритм заканчивается, когда не останется неотмаскированных кубов, либо маскирующий куб максимальной стоимости будет состоять только из одних μ (нулевая стоимость).

Таким образом, окончательное факторизованное покрытие будет выглядеть следующим образом