C2*A2 | 0x0x1 | 0x1x0 | 1x0x0 |
0x0x1 | |||
0x1x0 | 0xyxy | ||
1x0x0 | yx0xy | yxyx0 | |
1x1x1 | yxyx1 | yx1xy | 1xyxy |
Множество С3 – пустое.
Множество простых имплекант Z: 0x0x1; 0x1x0 1x0x0; 1x1x1.
Z#Z | 0x0x1 | 0x1x0 | 1x0x0 | 1x1x1 |
0x0x1 | - | 0x1x0 | 1x0x0 | 1x1x1 |
0x1x0 | 0x0x1 | - | 1x0x0 | 1x1x1 |
1x0x0 | 0x0x1 | 0x1x0 | - | 1x1x1 |
1x1x1 | 0x0x1 | 0x1x0 | 1x0x0 | - |
- | 0x0x1 | 0x1x0 | 1x0x0 | 1x1x1 |
С помощью операции пересечения находим L-экстремали образованные на множестве N.
L#E 00001 00011 00100 00110 01001 01011 01100 01110 10000 10010 10101 10111 11000 11010 11101 11111 0x0x1 00100 00110 01100 01110 10000 10010 10101 10111 11000 11010 11101 11111 0x1x0 10000 10010 10101 10111 11000 11010 11101 11111 1x0x0 10101 10111 11101 11111 1x1x1 |
Все L-экстремали, и только они входят в Cmin: 0x0x1; 0x1x0; 1x0x0; 1x1x1.
Алгоритм Рота для выхода S2 ОЧС:
С0=L; Z0=0;
Множество С0: 00001; 00010; 00110; 00111; 01000; 01011; 01100; 01101; 10010; 10011; 10100; 10111; 11000; 11001; 11101.
C0*C0 | 00001 | 00010 | 00110 | 00111 | 01000 | 01011 | 01100 | 01101 | 10010 | 10011 | 10100 | 10111 | 11000 | 11001 | 11101 |
00001 | |||||||||||||||
00010 | 000yy | ||||||||||||||
00110 | 00yyy | 00x10 | |||||||||||||
00111 | 00yy1 | 00y1y | 0011x | ||||||||||||
01000 | 0y00y | 0y0y0 | 0yyy0 | 0yyyy | |||||||||||
01011 | 0y0y1 | 0y01y | 0yy1y | 0yy11 | 010yy | ||||||||||
01100 | 0yy0y | 0yyy0 | 0y1y0 | 0y1yy | 01x00 | 01yyy | |||||||||
01101 | 0yy01 | 0yyyy | 0y1yy | 0y1y1 | 01y0y | 01yy1 | 0110x | ||||||||
10010 | y00yy | x0010 | y0y10 | y0y1y | yy0y0 | yy01y | yyyy0 | yyyyy | |||||||
10011 | y00y1 | y001y | y0y1y | y0y11 | yy0yy | yy011 | yyyyy | yyyy1 | 1001x | ||||||
10100 | y0y0y | y0yy0 | y01y0 | y01yy | yyy00 | yyyyy | yy100 | yy10y | 10yy0 | 10yyy | |||||
10111 | y0yy1 | y0y1y | y011y | x0111 | yyyyy | yyy11 | yy1yy | yy1y1 | 10y1y | 10x11 | 101yy | ||||
11000 | yy00y | yy0y0 | yyyy0 | yyyyy | x1000 | y10yy | y1y00 | y1y0y | 1y0y0 | 1y0yy | 1yy00 | 1yyyy | |||
11001 | yy001 | yy0yy | yyyyy | yyyy1 | y100y | y10y1 | y1y0y | y1y01 | 1y0yy | 1y0y1 | 1yy0y | 1yyy1 | 1100x | ||
11101 | yyy01 | yyyyy | yy1yy | yy1y1 | y1y0y | y1yy1 | y110y | x1101 | 1yyyy | 1yyy1 | 1y10y | 1y1y1 | 11y0y | 11x01 | |
11110 | yyyyy | yyy10 | yy110 | yy11y | y1yy0 | y1y1y | y11y0 | y11yy | 1yy10 | 1yy1y | 1y1y0 | 1y11y | 11yy0 | 11yyy | 111yy |
Множество C1:
00x10 x0010 0011x x0111 01x00 x1000 0110x x1101 1001x 10x11 1100x 11x01
C1=A1È(C0\Z0)
C1*A1 | 00x10 | x0010 | 0011x | x0111 | 01x00 | x1000 | 0110x | x1101 | 1001x | 10x11 | 1100x |
00x10 | |||||||||||
x0010 | 00010 | ||||||||||
0011x | 00110 | 00x10 | |||||||||
x0111 | 0011x | x0y1y | 00111 | ||||||||
01x00 | 0yxy0 | 0y0y0 | 0y1y0 | 0y1yy | |||||||
x1000 | 0y0y0 | xy0y0 | 0yyy0 | xyyyy | 01000 | ||||||
0110x | 0y1y0 | 0yyy0 | 0y1yx | 0y1y1 | 01100 | 01x00 | |||||
x1101 | 0y1yy | xyyyy | 0y1y1 | xy1y1 | 0110x | x1y0y | 01101 | ||||
1001x | x0010 | 10010 | y0y1x | 10x11 | yy0y0 | 1y0y0 | yyyyx | 1yyy1 | |||
10x11 | y0x1y | 1001x | x0111 | 10111 | yyxyy | 1y0yy | yy1y1 | 1y1y1 | 10011 | ||
1100x | yy0y0 | 1y0y0 | yyyyx | 1yyy1 | x1000 | 11000 | y1y0x | 11x01 | 1y0yx | 1y0y1 | |
11x01 | yyxyy | 1y0yy | yy1y1 | 1y1y1 | y1x0y | 1100x | x1101 | 11101 | 1y0y1 | 1yxy1 | 11001 |
Множество С2 - пустое
Множество простых имплекант Z: 00001; 01011; 10100; 11110; 00x10; x0010;
0011x; x0111; 01x00; x1000; 0110x; x1101; 1001x; 10x11; 1100x; 11x01.
00001 01011 10100 11110 00001 00001 O O O 00010 O O O O 00110 O O O O 00111 O O O O 01000 O O O O 01011 O 01011 O O 01100 O O O O 01101 O O O O 10010 O O O O 10011 O O O O 10100 O O 10100 O 10111 O O O O 11000 O O O O 11001 O O O O 11101 O O O O 11110 O O O 11110 |
Кубы на множестве L: 00001; 01011; 10100; 11110.
L-экстремали: 00001; 01011 10100; 11110.
L#E 00001 00010 00110 00111 01000 01011 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110 00001 00010 00110 00111 01000 01011 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110 01011 00010 00110 00111 01000 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110 10100 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 11110 11110 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 |
00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 00x10 00010 00110 O O O O O O O O O O x0010 00010 O O O O O 10010 O O O O O 0011x O 00110 00111 O O O O O O O O O x0111 O O 00111 O O O O O 10111 O O O 01x00 O O O 01000 01100 O O O O O O O x1000 O O O 01000 O O O O O 11000 O O 0110x O O O O 01100 01101 O O O O O O x1101 O O O O O 01101 O O O O O 11101 1001x O O O O O O 10010 10011 O O O O 10x11 O O O O O O O 10011 10111 O O O 1100x O O O O O O O O O 11000 11001 O 11x01 O O O O O O O O O O 11001 11101 |
Тупиковые формы: 00x10, x0111, 01x00, x1101, 1001x, 1100x
Cmin=00001; 01011 10100; 11110, 00x10, x0111, 01x00, x1101, 1001x, 1100x
Эффективность минимизации определяется коэфицентом минимизации. Он расчитывается по следующей формуле:
Цена исходного покрытия
Коэф.=-----------------------------------------
Цена минимального покрытия
Таблица 13. Коэфициент минимизации.
Цена исходного покрытия | Цена минимального покрытия | Коэфицент минимизации | |
Q1 | 84 | 6 | 14 |
Q2 | 84 | 35 | 2,4 |
P2 | 84 | 21 | 4 |
Синтез МПА делителя
Автомат должен управлять делением с восстановления остатка. Блок-схема этого алгоритма приведена ниже:
Y0 – суммирование делимого и двойного дополнительного кода делителя.;
Y1 – занесение нуля в регистр частного, восстановление остатка (суммирование делимого и делителя);
Y2 – занесение единицы в регистр частного;
Y3 – сдвиг регистра суммы и частного влего, наращивание точности частного;
X1 – проверка знакового разряда регистра суммы (0 – положительное, 1 - отрицательное);
X2 – проверка достижения точности вычисления;
По условию задачи делитель необходимо синтезировать в виде управляющего автомата Мура. Разметка ГСА в этом случае происходит по следующему алгоритму:
1. Меткой a1 отмечаются первая и последняя вершины.
2. Метками a2..am отмечаются все операторные вершины.
По отмеченной ГСА строится таблица переходов:
am | K(am) | as | F(am,as) | K(as) | X(am,as) | Y(am,as) |
A1 | 000 | A2 | 001 | 001 | -- | -- |
A2 | 001 | A3 | 011 | 010 | X1 | Y0 |
A2 | 001 | A4 | 010 | 011 | X1 | Y0 |
A3 | 010 | A5 | 110 | 100 | -- | Y1 |
A4 | 011 | A5 | 111 | 100 | -- | Y2 |
A5 | 100 | A2 | 101 | 001 | X2 | Y3 |
A5 | 100 | A1 | 100 | 000 | X2 | Y3 |
По построенной таблице сформируем таблицу истинности для настройки ПЛМ:
X1 | X2 | T1 | T2 | T3 | Y0 | Y1 | Y2 | Y3 | D1 | D2 | D3 |
- | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
0 | - | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
1 | - | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
- | - | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
- | - | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
- | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
- | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
По полученной таблице построим автомат, в качестве памяти используя T-триггеры.