Смекни!
smekni.com

Синтез цифровых схем арифметических устройств (стр. 6 из 6)

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.

Так как N={Æ} то всё Z образовано на множестве L.

Кубы на множестве L: 0x0x1; 0x1x0; 1x0x0; 1x1x1.

L-экстремали: 0x0x1; 0x1x0; 1x0x0; 1x1x1.

Проверим, не осталось ли кубов из L не покрытых L-экстремалями.


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-триггеры.