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

1

Оглавление

Постановка задачи

Исходные данные к курсовому проекту

Разработка алгоритма умножения

Разработка структурной схемы устройства

Синтез преобразователя множителя

Логический синтез одноразрядного четверичного умножителя-сумматора

Логический синтез одноразрядного четверичного сумматора

Синтез МПА делителя

Постановка задачи

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

По исходным данным необходимо разработать:

Алгоритм выполнения операции умножения, для чего потребуется:

перевести исходные числа из десятичной системы счисления в двоично-десятичную;

представить числа в форме с плавающей запятой;

произвести перемножение чисел по алгоритму “Г” в дополнительных разрядах на два разряда одновременно;

оценить погрешность вычисления после перевода результата в исходную систему счисления.

Алгоритм выполнения операций сложения и вычитания.

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

Функциональные схемы основных узлов проектируемого сумматора-умножителя в заданном логическом базисе. Для этого провести:

логический синтез комбинационного одноразрядного четверичного сумматора (ОЧС) на основе составленной таблицы истинности для суммы слагаемых с учетом переноса из младшего разряда, используя при этом алгоритм извлечения (Рота), и оценить эффективность минимизации;

логический синтез одноразрядного комбинационного четверичного умножителя-сумматора (ОЧУС), путем минимизации переключательных функций по каждому выходу схемы. Минимизация выполняется с применением карт Карно-Вейча с последующей оценкой эффективности минимизации;

логический синтез комбинационной схемы преобразователя множителя (ПМ);

построить функциональную схему ОЧС на мультиплексорах;

построить функциональную схему ПМ и ОЧУС в заданном базисе;

Определить время умножения на один разряд и на n разрядов множителя.

Разработать алгоритм выполнения операции деления.

Функциональную схему делителя, представив его как управляющий автомат, для чего необходимо:

построить граф связности автомата;

разметить его для синтеза автомата Мура;

построить таблицу переходов автомата;

определить переключательные функции выходных сигналов и сигналов обратной связи;

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

Исходные данные к курсовому проекту

В качестве исходных данных к курсовому проекту задается следующее:

Исходные операнды - десятичные числа с целой и дробной частью, над которыми производится операция умножения (36,39 & 53,25).

Алгоритм выполнения операции умножения Г.

Метод ускоренного умножения на базе которого строится умножитель:

умножение закодированного двоично-четверичного множимого на 2 разряда двоичного множителя одновременно в дополнительных кодах;

Преобразование множителя в обоих случаях производится для исключения из процесса умножения диады множителя 11.

Двоичные коды четверичных цифр множимого для работы в двоично-четверичной системе счисления (представляется кодом: 0₄ - 00, 1₄ - 11, 2₄ - 01, 3₄ - 10). Множитель представляется обычным весомозначным кодом: 0₄ - 00, 1₄ - 01, 2₄ - 10, 3₄ - 11.

Тип синтезируемого устройства умножения, определяемый основными структурными узлами, на базе которых строится умножитель:

умножитель 2-го типа строится на базе ОЧУС, ОЧС и регистра результата.

Способ минимизации и логический базис для аппаратной реализации ОЧС и ОЧУС (функционально полный базис представлен функцией x₁ + x ₂ :

Таблица 1. Таблица истинности:

X1	X2	1	не 1
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

ОЧС реализуется на мультиплексорах).

Алгоритм выполнения операции деления:

деление с восстановлением остатков;

Класс синтезируемого микропрограммного автомата: Мура.

Логический базис для аппаратной реализации делителя, как управляющего автомата: ПЛМ и триггеры для организации цепи обратной связи (Т -триггеры).

Разработка алгоритма умножения

Перевод сомножителей из десятичной системы счисления в четверичную:

МНОЖИМОЕ

36 | 4 0,39 Мн₄ =210,1203

36 9 | 4 4

0 8 2 1,56 Мн_2/4 = 011100,11010010

1 4

2,24

4

0,96

4

3,84

4

3,36

МНОЖИТЕЛЬ

53| 4 0,25 Мт₄ = 311,1

52 13 | 4 4 Мт_2/4 = 110101,01

1 12 3 1,00

1

Запишем сомножитель в форме с плавающей запятой в прямом коде:

Мн = 0,01110011010010 Р_мн = 0,0010 +03 закодирован по заданию

Мт = 0,11010101 Р_мт = 0,0011 +03 незакодирован по заданию

[Мт]_д = Мт = 0,3111₄ = 0,11010101_2/4

[Мт]_дп = 0,101010101_2/4

Мн = 0,2101203

[-Мн]_д = 3,1232131

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

Порядок произведения будет равен:

Р_мн = 0.0010₊ 03

Р_мт = 0.0011 03

Р = 0.1101 12

результат закодирован в соответствии с заданием на кодировку множимого.

Знак произведения определяется суммой по модулю два знаков сомножителей, т.е.:

зн Мн + зн Мт = 0 + 0 = 0.

Для умножения мантисс необходимо предварительно преобразовать множитель, чтобы исключить диаду 11(3₄), заменив ее на триаду 101.

Перемножение мантисс по алгоритму «Г» приведено втаблице 2:

[Мт]_дп = 0,101010101_2/4

Мн = 0,2101203

[-Мн]_д = 3,1232131

Таблица 2. Умножение по алгоритму “Г”.

Четверичная с/с
ЗНАК	РЕГИСТР РЕЗУЛЬТАТА	ДЕЙСТВИЯ
0.	000000000000
0.	000000000000	+0
0.	000000000000
0.	021012030000	+Мн>>1
0.	021012030000
3.	331232131000	-Мн>>2
10.	012310221000
0.	000210120300	+Мн>>3
10.	013121001300
0.	000021012030	+Мн>>4
0.	013202013330
0.	000002101203	+Мн>>5
0.	013210121133	Рез. В доп коде
0.	013210121133	Рез. В пр. коде
	132101,21133
	1937,5927734375	10 с/с

После окончания умножения необходимо оценить погрешность вычислений. Для этого полученное произведение (Мн*Мт₄=013210121133 Р_Мн*Мт = 6) приводится к нулевому порядку, а затем переводится в десятичную систему счисления:

Мн*Мт₄ = 132101,21133 Р_Мн*Мт = 0;

Мн*Мт₁₀ = 1937,5927734375.

Результат прямого перемножения операндов дает следующее значение:

Мн₁₀*Мт₁₀ = 36,39 * 53,25 = 1937,7675.

Абсолютная погрешность:

= 1937,7675 - 1937,5927734375 = 0,17473.

Относительная погрешность:

0,17473

d--=----------------------------=------------------------------------------=----_,____9_17-- (d = 0,00901%)

------------Мн*Мт 1937,7675

Эта погрешность является суммарной, накопленной за счет приближенного перевода из 10 с/с в четверичную обоих сомножителей, а также за счет округления полученного результата произведения.

В случае отрицательного множимого:

[Мт]_дп = 0,101010101_2/4

Мн = - 0,2101203

[Мн]_д = 3,1232131

[-Мн]_д = 0,2101203

Четверичная с/с
ЗНАК	РЕГИСТР РЕЗУЛЬТАТА	ДЕЙСТВИЯ
0.	000000000000
0.	000000000000	+0
0.	000000000000
3.	312321310000	+Мн>>1
3.	312321310000
0.	002101203000	-Мн>>2
3.	321023113000
3.	333123213100	+Мн>>3
10.	320212332100
3.	333312321310	+Мн>>4
10.	320131320010
3.	333331232131	+Мн>>5
10.	320123212201	Рез. В доп коде
1. 3 - 4=1	013210121133	Рез. В пр. коде
	132101,21133
	1937,5927734375	10 с/с

Разработка структурной схемы устройства

Структурная схема строится на основе следующих блоков

Многоразрядный регистр сдвига

 сдвиг

Dn Q1

С Qn

S1

S2

“+1”

Предназначен для хранения и сдвига n-разрядного значения числа. Регистр имеет n информационных входов D1 - Dn , управляющий вход разрешения записи в регистр С , управляющие входы сдвига содержимого регистра влево S1 и вправо S2 , управляющий вход добавления 1 к содержимому регистра “+1”, и n выходов Q1- Qn . Все управляющие функции выполняются при поступлении 1 на соответствующий управляющий вход.

Разрядность регистра результата должна быть на единицу больше, чем разрядность исходных слагаемых, чтобы предусмотреть возможность возникновения при суммировании переноса.

Одноразрядный четверичный умножитель - сумматор (ОЧУС)

 R

P2 Р1

от младшего

ОЧУС

ОЧУС

к старшему

ОЧУС

Мн Мт

ОЧУС предназначен для получения одной четверичной цифры путем перемножения диады множимого (Мн) и диады множителя (Мт), и прибавления к полученному результату переноса от младшего ОЧУС (P1).

Если устройство работает как сумматор, то оба слагаемых последовательно (за 2 такта) заносятся в регистр множимого, а на управляющий вход ФДК F₂ поступает «1». На выходах ФДК формируется дополнительный код первого слагаемого с учетом знака. Первое слагаемое без изменений должно быть записано в регистр результата, поэтому управляющие сигналы, поступающие на входы «h» всех ОЧУС, позволяют переписать на выходы ОЧУС разряды первого слагаемого без изменений. Если на вход «h» поступает «0», то ОЧУС перемножает разряды Мн и Мт и добавляет к полученному результату перенос из предыдущего ОЧУС.

Если устройство работает как умножитель, то множимое и множитель помещаются в соответствующие регистры, а на управляющий вход ФДК F₂ поступает «0». Диада множителя поступает на входы ПМ.

Т.к. на входы ОЧУС из регистра Мт не могут прийти коды «3», в таблице истинности работы ОЧУС будут содержаться 16 безразличных входных наборов.

После ОЧУС частичные произведения складываются между собой в ОЧС (на первом такте идет сложение с нулем).

Частичные суммы хранятся в регистре результата.

Одноразрядный четверичный сумматор (ОЧС)

S

P2 P1

А В

Предназначен для суммирования двух четверичных цифр и прибавления к полученной сумме единицы переноса от предыдущего ОЧС. Формирует единицу переноса в следующий ОЧС.

В ОЧС первое слагаемое складывается с нулем, записанным в регистре результата, и переписывается без изменений в регистр результата. На втором такте второе слагаемое из регистра множимого через цепочку ОЧУС попадает на входы ОЧС и складывается с первым слагаемым, хранящимся в регистре результата. Сумма хранится в регистре результата. Если устройство работает как сумматор, никаких сдвигов содержимого регистров не производится.

Многоразрядный формирователь дополнительного кода (ФДК)

 Знак Yn Y1

f1

f2

Знак Xn X1

Предназначен для получения дополнительного кода многоразрядного четверичного числа. ФДК имеет n двоичных входов (Х1-Хn), n двоичных выходов (Y1-Yn), отдельный вход для знака преобразуемого числа, а также управляющие входы (f1) и (f2). При подаче управляющего сигнала (“1”) на вход f1 ФДК формирует дополнительный код числа в сооответствии с его знаком. При подаче управляющего сигнала (“1”) на вход f2 ФДК формирует двойной дополнительный код числа. Принцип работы ФДК в зависимости от управляющих сигналов см. в табл.3.

Таблица 3. Работа ФДК.

F1 F2	РЕЗУЛЬТАТ НА ВЫХОДАХ ФДК
0 0	доп. код множимого
0 1	доп. код слагаемого
1 0	двойной доп. код множимого (меняет знак Мн)
1 1	доп. код слагаемого

Синтез преобразователя множителя

Задачей ПМ является исключить из множителя диады 11, заменив их на триады. Регистр множителя является сдвиговым, после каждого такта умножение его содержимое сдвигается на 2 двоичных разряда, и в конце умножения регистр обнуляется. Выход 3 ПМ переходит в единичное состояние, если текущая диада содержит отрицание ( 01 ). В этом случае инициализируется управляющий вход F₁ формирователя дополнительного кода (ФДК), и на выходах ФДК формируется двойной дополнительный код множимого (умножение на -1).

На выходах 1,2 ПМ формируются диады преобразованного множителя, которые поступают на входы ОЧУС вместе с диадами множимого. На трех выходах ОЧУС формируется результат умножения диад Мн * Мт + перенос из предыдущего ОЧУС. Максимальной цифрой в диаде преобразованного множителя является двойка, поэтому перенос, формируемый ОЧУС ,может быть только двоичным:

3 * 2 = 1 2

max maх max

Мн Мт перенос

Табл.4. Таблица истинности преобразователя множителя.

D1	D2	D3	P1	P2	F
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	0	1	0
0	1	1	1	0	0
1	0	0	1	0	1
1	0	1	0	1	1
1	1	0	0	1	1
1	1	1	0	0	0

Исходя из выше изложенной таблицы синтезируется схема.

_ _ _ _ _ _ _ _
F=x1x2x3+x1x2x3+x1x2x3=x1x2+x1x3=x1(x2+x3)
_ _ _
P1=x1x2x3+x1x2x3
_ _ _ _ _ _ _ _
P2=x1x2x3+x1x2x3+x1x2x3+x1x2x3=x2x3+x2x3=x2x3



Преобразователь множителя.

Структурная схема устройства приведена на рисунке в приложении. Она содержит регистры: множимого (Рг Мн), множителя (Рг Мт), результата (Рг Рез), формирователи дополнительного кода (ФДК) , 16 блоков ОЧС, 15 блоков ОЧУС и преобразователь множителя (ПМ).

Устройство умножения работает следующим образом:

Исходные сомножители записываются в регистры ( Рг Мн, Рг Мт) Рг Рез обнуляется.

С выходов ФДК на входы ОЧУС поступают по 2 двоичные цифры. Результат операции поступает в ОЧС, где суммируется с содержимым Рг Рез и записывается снова в Рг Рез.

После проведения этих операций происходит сдвиг Рг Мн , Рг Мт .

Если на вход “h” подаётся “1” то ОЧУС становятся “прозрачными” и устройство работает как сумматор благодаря ОЧС. Слогаемые последовательно (за 2 такта) заносятся в регистр множимого.

Временные затраты на умножение сомножителей определяются в основном затратами на образование частичных произведений, получаемых на выходах ОЧУС, и примерно равны:

Ту = 8(tсдв + tПМ + tФДК + 15tОЧУС + 16tОЧС), где:

tОЧС- время формирования единицы переноса в ОЧС

tОЧУС - время умножения на одном ОЧУС

tсдв -время сдвига множимого (множителя)

tПМ - время задержки в преобразователе множителя

tФДК - время задержки на ФДК

На самом деле, операции выполняются параллельно в нескольких узлах, и время задержки будет определятся наибольшей составляющей (либо 15tОЧУС, либо 15tОЧУС, в зависимости от конкретной реализации).

Логический синтез одноразрядного четверичного умножителя-сумматора

ОЧУС - это комбинационное устройство, имеющее 6 входов (2 разряда из регистра МН, 2 разряда из регистра Мт, вход переноса и управляющий вход h) и 3 выхода. Принцип работы ОЧУС описывается с помощью таблицы истинности (табл.5).

Разряды множителя закодированы : 0 - 00; 1 - 01; 2 - 10; 3 - 11.

Разряды множимого закодированы : 0 - 00; 1 - 11; 2 - 01; 3 - 10.

Управляющий вход h определяет тип операции: 0 - умножение закодированных цифр, поступивших на информационные входы, и добавление переноса; 1 - вывод на выходы без изменения значения разрядов, поступивших из регистра множимого.

Табл. 5

пер.	Мн	Мт	упр.		Перенос	Результат	Результат операции
Р1	Х1	Х2	У1	У2	h		Р	Q1	Q2	В четверичной с/с
0	0	0	0	0	0		0	0	0	0*0+0=00
0	0	0	0	0	1		0	0	0	Выход - код «00»
0	0	0	0	1	0		0	0	0	0*1+0=00
0	0	0	0	1	1		0	0	0	Выход - код «00»
0	0	0	1	0	0		0	0	0	0*2+0=00
0	0	0	1	0	1		0	0	0	Выход - код «00»
0	0	0	1	1	0		Х	Х	Х	0*3+0=00	*
0	0	0	1	1	1		Х	Х	Х	Выход - код «00»	*
0	0	1	0	0	0		0	0	0	2*0+0=00
0	0	1	0	0	1		0	0	1	Выход - код «02»
0	0	1	0	1	0		0	0	1	2*1+0=02
0	0	1	0	1	1		0	0	1	Выход - код «02»
0	0	1	1	0	0		1	0	0	2*2+0=10
0	0	1	1	0	1		0	0	1	Выход - код «02»
0	0	1	1	1	0		Х	Х	Х	2*3+0=12	*
0	0	1	1	1	1		Х	Х	Х	Выход - код «02»	*
0	1	0	0	0	0		0	0	0	3*0+0=00
0	1	0	0	0	1		0	1	0	Выход - код «03»
0	1	0	0	1	0		0	1	0	3*1+0=03
0	1	0	0	1	1		0	1	0	Выход - код «03»
0	1	0	1	0	0		1	0	1	3*2+0=12
0	1	0	1	0	1		0	1	0	Выход - код «03»
0	1	0	1	1	0		Х	Х	Х	3*3+0=21	*
0	1	0	1	1	1		Х	Х	Х	Выход - код «03»	*
0	1	1	0	0	0		0	0	0	1*0+0=00
0	1	1	0	0	1		0	1	1	Выход - код «01»
0	1	1	0	1	0		0	1	1	1*1+0=01
0	1	1	0	1	1		0	1	1	Выход - код «01»
0	1	1	1	0	0		0	0	1	1*2+0=02
0	1	1	1	0	1		0	1	1	Выход - код «01»
0	1	1	1	1	0		Х	Х	Х	1*3+0=03	*
0	1	1	1	1	1		Х	Х	Х	Выход - код «01»	*
1	0	0	0	0	0		0	1	1	0*0+1=01
1	0	0	0	0	1		0	0	0	Выход - код «00»
1	0	0	0	1	0		0	1	1	0*1+1=01
1	0	0	0	1	1		0	0	0	Выход - код «00»
1	0	0	1	0	0		0	1	1	0*2+1=01
1	0	0	1	0	1		0	0	0	Выход - код «00»
1	0	0	1	1	0		Х	Х	Х	0*3+1=01	*
1	0	0	1	1	1		Х	Х	Х	Выход - код «00»	*
1	0	1	0	0	0		0	1	1	2*0+1=01
1	0	1	0	0	1		0	0	1	Выход - код «02»
1	0	1	0	1	0		0	1	0	2*1+1=03
1	0	1	0	1	1		0	0	1	Выход - код «02»
1	0	1	1	0	0		1	1	1	2*2+1=11
1	0	1	1	0	1		0	0	1	Выход - код «02»
1	0	1	1	1	0		Х	Х	Х	2*3+1=13	*
1	0	1	1	1	1		Х	Х	Х	Выход - код «02»	*
1	1	0	0	0	0		0	1	1	3*0+1=01
1	1	0	0	0	1		0	1	0	Выход - код «03»
1	1	0	0	1	0		1	0	0	3*1+1=10
1	1	0	0	1	1		0	1	0	Выход - код «03»
1	1	0	1	0	0		1	1	0	3*2+1=13
1	1	0	1	0	1		0	1	0	Выход - код «03»
1	1	0	1	1	0		Х	Х	Х	3*3+1=12	*
1	1	0	1	1	1		Х	Х	Х	Выход - код «03»	*
1	1	1	0	0	0		0	1	1	1*0+1=01
1	1	1	0	0	1		0	1	1	Выход - код «01»
1	1	1	0	1	0		0	0	1	1*1+1=02
1	1	1	0	1	1		0	1	1	Выход - код «01»
1	1	1	1	0	0		0	1	0	1*2+1=03
1	1	1	1	0	1		0	1	1	Выход - код «01»
1	1	1	1	1	0		Х	Х	Х	1*3+1=10	*
1	1	1	1	1	1		Х	Х	Х	Выход - код «01»	*

В таблице выделено 16 безразличных наборов, т.к. на входы ОЧУС из разрядов множителя не может поступить код 11.

Таблица 6. Шестнадцать безразличных наборов для ОЧУС.

P1	X1	X2	Y1	Y2	H
0	0	0	1	1	0
0	0	0	1	1	1
0	0	1	1	1	0
0	0	1	1	1	1
0	1	0	1	1	0
0	1	0	1	1	1
0	1	1	1	1	0
0	1	1	1	1	1
1	0	0	1	1	0
1	0	0	1	1	1
1	0	1	1	1	0
1	0	1	1	1	1
1	1	0	1	1	0
1	1	0	1	1	1
1	1	1	1	1	0
1	1	1	1	1	1

Таблица 7. Единичные наборы для выхода Q1 ОЧУС:

P1	X1	X2	Y1	Y2	h
0	1	0	0	0	1
0	1	0	0	1	0
0	1	0	0	1	1
0	1	0	1	0	1
0	1	1	0	0	1
0	1	1	0	1	0
0	1	1	0	1	1
0	1	1	1	0	1
1	0	0	0	0	0
1	0	0	0	1	0
1	0	0	1	0	0
1	0	1	0	0	0
1	0	1	0	1	0
1	0	1	1	0	0
1	1	0	0	0	0
1	1	0	0	0	1
1	1	0	0	1	1
1	1	0	1	0	0
1	1	0	1	0	1
1	1	1	0	0	0
1	1	1	0	0	1
1	1	1	0	1	1
1	1	1	1	0	0
1	1	1	1	0	1

Таблица 8. Карта Карно-Вейча для единичных наборов выхода Q1 ОЧУС:

1		*	1		*	1
1	1	*	1	1	*	1	1
1	1	*	1	1	*	1	1
1		*	1		*	1
1	1	*	1		*
		*			*
		*			*
1	1	*	1		*

Q1 = X1 H + P1 X1 Y2 + P1 Y2 H + P1 X1 H =

= X1(H + P1 Y2) + P1 H(Y2 X1)

Таблица 9. Единичные наборы для выхода Q2 ОЧУС:

P1	X1	X2	Y1	Y2	h
0	0	1	0	0	1
0	0	1	0	1	0
0	0	1	0	1	1
0	0	1	1	0	1
0	1	0	1	0	0
0	1	1	0	0	1
0	1	1	0	1	0
0	1	1	0	1	1
0	1	1	1	0	0
0	0	1	1	0	1
1	0	0	0	0	0
1	0	0	0	1	0
1	0	0	1	0	0
1	0	1	0	0	0
1	0	1	0	0	1
1	0	1	0	1	1
1	0	1	1	0	0
1	1	1	1	0	1
1	1	0	0	0	0
1	1	1	0	0	0
1	1	1	0	0	1
1	1	1	0	1	0
1	1	1	0	1	1
1	1	1	1	0	1

Таблица 10. Карта Карно-Вейча для нулевых наборов выхода Q2 ОЧУС:

	1	*	1		*	1	1
1	1	*	1	1	*	1	1
		*			*
		*	1		*		1
	1	*		1	*		1
		*			*
1	1	*	1	1	*	1	1
		*		1	*	1	1

Q2=(X2+H)*(P1+X2+Y1)*(P1+Y1+Y2+H)*(X1+X2+Y2)*(P1+X1+Y1+Y2+H)* *(P1+X1+X2+Y2+H)*(P1+X1+Y1+H)

Таблица 11. Единичные наборы для выхода переноса ОЧУС P2:

P1	X1	X2	Y1	Y2	h
0	0	1	1	0	0
0	1	0	1	0	0
1	0	1	1	0	0
1	1	0	0	1	0
1	1	0	1	0	0

Таблица 12. Карта Карно-Вейча для единичных наборов выхода переноса ОЧУС P:

	1	*	1	1	*
		*			*
		*			*
		*			*
		*	1	1	*
		*			*
		*			*
		*			*

P = X1 X2 Y1 H + X1 X2 Y1 H + P1 X1 X2 Y2 H =

= H X2 X1 (Y1 + P1 Y2) + X1 X2 Y1 H = H(X1 X2 Y1 + X1 X2(Y1 + P1 Y2))

Эффективность минимизации определяется коэфицентом минимизации. Он расчитывается по следующей формуле:

Цена исходного покрытия

Коэф.=-----------------------------------------

Цена минимального покрытия

Таблица 13. Коэфициент минимизации.

	Цена исходного покрытия	Цена минимального покрытия	Коэфицент минимизации
Q1	154	15	10,27
Q2	154	32	4,81
P2	35	14	2,5

Логический синтез одноразрядного четверичного сумматора

ОЧС - это комбинационное устройство, имеющее 5 входов (2 разряда одного слагаемого, 2 разряда второго слагаемого и вход переноса) и 3 выхода. Принцип работы ОЧС описывается с помощью таблицы истинности (табл.3).

Разряды обоих слагаемых закодированы: 0 - 00; 1 - 11; 2 - 01; 3 - 10.

Таблица истинности функционирования ОЧС строится для пяти переменных, четыре из которых (А1, А2, В1, В2) являются выходами ОЧУС, а пятая - межразрядный перенос из ОЧС смежного старшего разряда устройства умножения. Четверичная цифра суммы как диада S1S2 в таблице истинности образуется с учётом принятого кодирования четверичных цифр.

Табл. 14

A1	A2	В1	В2	p	P	S1	S2	в четверичной с/с
0	0	0	0	0	0	0	0	0+0+0=00
0	0	0	0	1	0	1	1	0+0+1=01
0	0	0	1	0	0	0	1	0+2+0=02
0	0	0	1	1	0	1	0	0+2+1=03
0	0	1	0	0	0	1	0	0+3+0=03
0	0	1	0	1	1	0	0	0+3+1=10
0	0	1	1	0	0	1	1	0+1+0=01
0	0	1	1	1	0	0	1	0+1+1=02
0	1	0	0	0	0	0	1	2+0+0=02
0	1	0	0	1	0	1	0	2+0+1=03
0	1	0	1	0	1	0	0	2+2+0=10
0	1	0	1	1	1	1	1	2+2+1=11
0	1	1	0	0	1	1	1	2+3+0=11
0	1	1	0	1	1	0	1	2+3+1=12
0	1	1	1	0	0	1	0	2+1+0=03
0	1	1	1	1	1	0	0	2+1+1=10
1	0	0	0	0	0	1	0	3+0+0=03
1	0	0	0	1	1	0	0	3+0+1=10
1	0	0	1	0	1	1	1	3+2+0=11
1	0	0	1	1	1	0	1	3+2+1=12
1	0	1	0	0	1	0	1	3+3+0=12
1	0	1	0	1	1	1	0	3+3+1=13
1	0	1	1	0	1	0	0	3+1+0=10
1	0	1	1	1	1	1	1	3+1+1=11
1	1	0	0	0	0	1	1	1+0+0=01
1	1	0	0	1	0	0	1	1+0+1=02
1	1	0	1	0	0	1	0	1+2+0=03
1	1	0	1	1	1	0	0	1+2+1=10
1	1	1	0	0	1	0	0	1+3+0=10
1	1	1	0	1	1	1	1	1+3+1=11
1	1	1	1	0	0	0	1	1+1+0=02
1	1	1	1	1	0	1	0	1+1+1=03

Безразличные наборы в таблице истинности отсутствуют т.к. со старших выходов ОЧУС могут прийти коды 0, 1, 2 и 3.

Таблица 15. Единичные наборы для выхода переноса P ОЧС.

A1	A2	В1	В2	p
0	0	1	0	1
0	1	0	1	0
0	1	0	1	1
0	1	1	0	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0
1	0	0	1	1
1	0	1	0	0
1	0	1	0	1
1	0	1	1	0
1	0	1	1	1
1	1	0	1	1
1	1	1	0	0
1	1	1	0	1

Таблица 16. Единичные наборы для выхода S1 ОЧС.

A1	A2	В1	В2	p
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

Таблица 17. Единичные наборы для выхода S2 ОЧС.

A1	A2	В1	В2	p
0	0	0	0	1
0	0	0	1	0
0	0	1	1	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	0	1
1	0	0	1	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	0	1
1	1	1	0	1
1	1	1	1	0

Алгоритм Рота для выхода переноса ОЧС

Отыскание множества L-экстремалей

Z0={}; C0=L;

Множество С0: 11101; 00101; 01010; 01011; 01100; 01101; 01111; 10001;

10010; 10011; 10100; 10101; 10110; 10111; 11011.

C0*C0

11101

00101

01010

01011

01100

01101

01111

10001

10010

10011

10100

10101

10110

10111

11011

11101

00101

yy101

01010

y1yyy

0yyyy

01011

y1yy1

0yyy1

0101x

01100

y110y

0y10y

01yy0

01yyy

01101

x1101

0x101

01yyy

01yy1

0110x

01111

y11y1

0y1y1

01y1y

01x11

011yy

011x1

10001

1yy01

y0y01

yy0yy

yy0y1

yyy0y

yyy01

yyyy1

10010

1yyyy

y0yyy

yy010

yy01y

yyyy0

yyyyy

yyy1y

100yy

10011

1yyy1

y0yy1

yy01y

yy011

yyyyy

yyyy1

yyy11

100x1

1001x

10100

1y10y

y010y

yyyy0

yyyyy

yy100

yy10y

yy1yy

10y0y

10yy0

10yyy

10101

1x101

x0101

yyyyy

yyyy1

yy10y

yy101

yy1y1

10x01

10yyy

10yy1

1010x

10110

1y1yy

y01yy

yyy10

yyy1y

yy1y0

yy1yy

yy11y

10yyy

10x10

10y1y

101x0

101yy

10111

1y1y1

y01y1

yyy1y

yyy11

yy1yy

yy1y1

yy111

10yy1

10y1y

10x11

101yy

101x1

1011x

11011

11yy1

yyyy1

y101y

x1011

y1yyy

y1yy1

y1y11

1y0y1

1y01y

1x011

1yyyy

1yyy1

1yy1y

1yy11

11100

1110x

yy10y

y1yy0

y1yyy

x1100

y110y

y11yy

1yy0y

1yyy0

1yyyy

1x100

1y10y

1y1y0

1y1yy

11yyy

Кубы, образовавшиеся в этой таблице, образуют множество A1. Множество C1 получаем по формуле: C1=A1(C0-Z0)

Множество C1: x1101; 1x101; 1110x; 0x101; x0101; 0101x; 01x11; x1011; 0110x; x1100; 011x1; 100x1; 10x01; 1001x; 10x10; 10x11; 1x011; 1010x; 101x0; 1x100; 101x1; 1011x.

C1*A1

x1101

1x101

1110x

0x101

x0101

0101x

01x11

x1011

0110x

x1100

011x1

100x1

10x01

1001x

10x10

10x11

x011

1010x

101x0

1x100

101x1

x1101

1x101

11101

1110x

11101

11101

0x101

01101

xx101

x1101

x0101

xx101

10101

1x101

00101

0101x

01yy1

y1yy1

y1yyx

01yy1

0yyy1

01x11

011x1

y11y1

y11y1

011x1

0y1y1

01011

x1011

x1yy1

11yy1

11yy1

01yy1

xyyy1

01011

01011

0110x

01101

x1101

x110x

01101

0x101

01yyx

011x1

01yy1

x1100

x110x

1110x

11100

0110x

xy10y

01yy0

011yy

x1yyy

01100

011x1

01101

x1101

x1101

01101

0x101

01x11

01111

01x11

01101

0110x

100x1

1yy01

10x01

1yy01

y0y01

10x01

yy011

yy011

1x011

yyy01

1yy0y

yyyx1

10x01

1x101

10101

1x101

x0101

10101

yy0y1

yyxy1

1y0y1

yy101

1y10y

yy101

10001

1001x

1yyy1

10yy1

1yyyx

y0yy1

10yy1

yy01x

yy011

1x011

yyyyx

1yyy0

yyy11

10011

100x1

10x10

1y1yy

101yy

1y1y0

y01yy

101yy

yy010

yyx1y

1y01y

yy1y0

1y1y0

yy11y

1001x

10xyy

10010

10x11

1y1y1

101x1

1y1y1

y01y1

101x1

yy011

yyx11

1x011

yy1y1

1y1yy

yy111

10011

10xx1

10011

10x1x

1x011

11yy1

1xyy1

11yy1

yxyy1

10yy1

x1011

x1011

11011

y1yy1

11yyy

y1y11

10011

100x1

10011

1001x

10011

1010x

1x101

10101

1x10x

x0101

10101

yyyyx

yy1y1

1yyy1

yy10x

1x100

yy101

10x01

10101

10yyx

101x0

101x1

10yy1

101x0

1y10y

1010x

1x100

y010y

1010x

yyy10

yy11y

1yy1y

yy100

1x100

yy1xy

10yxy

1010x

10x10

10110

1011x

10y1y

10100

1x100

1110x

1x10x

11100

yx10y

1010x

y1yy0

y11yy

11yyy

x1100

11100

y110y

10y0y

1010x

10yy0

101x0

101yy

1xyyy

10100

10100

101x1

1x101

10101

1x101

x0101

10101

yyy11

yy111

1yy11

yy101

1y10y

yy1x1

10xx1

10101

10x11

1011x

10111

10x11

10101

101xx

1010x

1011x

1y1y1

101x1

1y1yx

y01y1

101x1

yyy1x

yy111

1yy11

yy1yx

1y1y0

yy111

10x11

101x1

10x1x

10110

10111

10x11

101xx

10110

101x0

10111

Множество C2: xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx.

*	xx101	x110x	1x10x	10xx1	10x1x
xx101
x110x	x1101
1x10x	1x101	1110x
10xx1	10101	1x101	10101
10x1x	101x1	1y1yx	101xx	10x11
101xx	10101	1x10x	1010x	101x1	1011x

Множество С3 - пустое (склеивание не дало новых кубов более высокой размерности).

Множество простых имплекант Z: 0101x; 01x11; x1011; 011x1; 1x011; xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx.

Отбросим те кубы из множества Z, которые покрываются другими.

Z#z 0101x 01x11 x1011 011x1 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx 0101x _ 01111 11011 011x1 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx 01x11 01010 _ 11011 01101 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx x1011 01010 01111 _ 01101 10011 xx101 x110x 1x10x 10xx1 10x1x 101xx 011x1 01010 11011 _ 10011 1x101 1110x 1x10x 10xx1 10x1x 101xx x0101 x1100 1x011 01010 01101 _ 1x101 1110x 1x10x 101x1 1011x 101xx x0101 x1100 10x01 10x10 xx101 01010 10011 _ 11100 1x100 10111 1011x 1011x x1100 10001 10x10 101x0 x110x 01010 10011 10101 _ 10100 10111 1011x 1011x x0101 10001 10x10 101x0 1x10x 01010 10011 _ 10111 1011x 1011x 00101 01100 10001 10x10 10110 10xx1 01010 00101 01100 10100 _ 10110 10110 10x10 10x1x 01010 00101 01100 10100 _ 10001 101xx 01010 00101 01100 10001 _ 10010 01010 00101 01100 10001 10010

С помощью операции пересечения находим L-экстремали образованные на множестве N.

Z#(Z-z)L 01010 00101 01100 10001 10010 11101 O O O O O 00101 O 00101 O O O 01010 01010 O O O O 01011 O O O O O 01100 O O 01100 O O 01101 O O O O O 01111 O O O O O 10001 O O O 10001 O 10010 O O O O 10010 10011 O O O O O 10100 O O O O O 10101 O O O O O 10110 O O O O O 10111 O O O O O 11011 O O O O O 11100 O O O O O

N={}

Кубы на множестве L: 01010; 00101; 01100; 10001; 10010.

L-экстремали: 0101x; xx101; x110x; 10xx1; 10x1x.

Найдём кубы из L не покрытые L-экстремалями.

L#E 11101 00101 01010 01011 01100 01101 01111 10001 10010 10011 10100 10101 10110 10111 11011 11100 0101x 11101 00101 01100 01101 01111 10001 10010 10011 10100 10101 10110 10111 11011 11100 xx101 01100 01111 10001 10010 10011 10100 10110 10111 11011 11100 x110x 01111 10001 10010 10011 10100 10110 10111 11011 10xx1 01111 10010 10100 10110 11011 10x1x 01111 10100 11011 01111 10100 11011

Из оставшегося Z (за исключением L-экстремалей) выберем кубы которые покроют остаток множества L.

(Z\E)(L#E)01111 10100 01x11 01111 O x1011 O O 011x1 01111 O 1x011 O O 1x10x O 10100 101xx O 10100

Тупиковые формы: 01x11, 011x1 & 1x10x, 101xx

Минимизированная переключательная функция для выхода переноса ОЧС C_min:

0101x; xx101; x110x; 10xx1; 10x1x; 01x11; 101xx.

Алгоритм Рота для выхода S1 ОЧС

C0=L; Z0=0;

Множество С0: 00001; 00011; 00100; 00110; 01001; 01011; 01100; 01110; 10000

10010; 10101; 10111; 11000; 11010; 11101

C0*C0

00001

00011

00100

00110

01001

01011

01100

01110

10000

10010

10101

10111

11000

11010

11101

00001

00011

000x1

00100

00y0y

00yyy

00110

00yyy

00y1y

001x0

01001

0x001

0y0y1

0yy0y

0yyyy

01011

0y0y1

0x011

0yyyy

0yy1y

010x1

01100

0yy0y

0yyyy

0x100

0y1y0

01y0y

01yyy

01110

0yyyy

0yy1y

0y1y0

0x110

01yyy

01y1y

011x0

10000

y000y

y00yy

y0y00

y0yy0

yy00y

yy0yy

yyy00

yyyy0

10010

y00yy

y001y

y0yy0

y0y10

yy0yy

yy01y

yyyy0

yyy10

100x0

10101

y0y01

y0yy1

y010y

y01yy

yyy01

yyyy1

yy10y

yy1yy

10y0y

10yyy

10111

y0yy1

y0y11

y01yy

y011y

yyyy1

yyy11

yy1yy

yy11y

10yyy

10y1y

101x1

11000

yy00y

yy0yy

yyy00

yyyy0

y100y

y10yy

y1y00

y1yy0

1x000

1y0y0

1yy0y

1yyyy

11010

yy0yy

yy01y

yyyy0

yyy10

y10yy

y101y

y1yy0

y1y10

1y0y0

1x010

1yyyy

1yy1y

110x0

11101

yyy01

yyyy1

yy10y

yy1yy

y1y01

y1yy1

y110y

y11yy

1yy0y

1yyyy

1x101

1y1y1

11y0y

11yyy

11111

yyyy1

yyy11

yy1yy

yy11y

y1yy1

y1y11

y11yy

y111y

1yyyy

1yy1y

1y1y1

1x111

11yyy

11y1y

111x1

C1=A1(C0-Z0)

Множество C1: 000x1; 0x001; 0x011; 001x0; 0x100; 0x110; 010x1; 011x0; 100x0; 1x000; 1x010; 101x1; 1x101; 1x111; 110x0; 111x1.

C1*A1

000x1

0x001

0x011

001x0

0x100

0x110

010x1

011x0

100x0

1x000

1x010

101x1

1x101

1x111

110x0

000x1

0x001

00001

0x011

00011

0x0x1

001x0

00yxy

00y0y

00y1y

0x100

00y0y

0xy0y

0xyyy

00100

0x110

00y1y

0xyyy

0xy1y

00110

0x1x0

010x1

0x0x1

01001

01011

0yyxy

01y0y

01y1y

011x0

0yyxy

01y0y

01y1y

0x1x0

01100

01110

01yxy

100x0

y00xy

y000y

y001y

y0yx0

y0y00

y0y10

yy0xy

yyyx0

1x000

y000y

yx00y

yx0yy

y0y00

yxy00

yxyy0

y100y

y1y00

10000

1x010

y001y

yx0yy

yx01y

y0y10

yxyy0

yxy10

y101y

y1y10

10010

1x0x0

101x1

y0yx1

y0y01

y0y11

y01xy

y010y

y011y

yyyx1

yy1xy

10yxy

10y0y

10y1y

1x101

y0y01

yxy01

yxyy1

y010y

yx10y

yx1yy

y1y01

y110y

10y0y

1xy0y

1xyyy

10101

1x111

y0y11

yxyy1

yxy11

y011y

yx1yy

yx11y

y1y11

y111y

10y1y

1xyyy

1xy1y

10111

1x1x1

110x0

yy0xy

y100y

y101y

yyyx0

y1y00

y1y10

y10xy

y1yx0

1x0x0

11000

11010

1yyxy

11y0y

11y1y

111x1

yyyx1

y1y01

y1y11

yy1xy

y110y

y111y

y1yx1

y11xy

1yyxy

11y0y

11y1y

1x1x1

11101

11111

11yxy

Множество C2: 0x0x1; 0x1x0; 1x0x0; 1x1x1.

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.

Z#(Z-z)L 0x0x1 0x1x0 1x0x0 1x1x1 00001 00001 O O O 00011 00011 O O O 00100 O 00100 O O 00110 O 00110 O O 01001 01001 O O O 01011 01011 O O O 01100 O 01100 O O 01110 O 01110 O O 10000 O O 10000 O 10010 O O 10010 O 10101 O O O 10101 10111 O O O 10111 11000 O O 11000 O 11010 O O 11010 O 11101 O O O 11101 11111 O O O 11111

Так как 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-экстремали, и только они входят в C_min: 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

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