Оглавление
Постановка задачи
Исходные данные к курсовому проекту
Разработка алгоритма умножения
Разработка структурной схемы устройства
Синтез преобразователя множителя
Логический синтез одноразрядного четверичного умножителя-сумматора
Логический синтез одноразрядного четверичного сумматора
Синтез МПА делителя
Постановка задачи
Курсовой проект предполагает синтез цифровых схем арифметических устройств, выполняющих операции сложения, вычитания, умножения и деления над числами, представленными в форме с плавающей запятой в двоичной и двоично-четверичной системах счисления.
По исходным данным необходимо разработать:
1. Алгоритм выполнения операции умножения, для чего потребуется:
- перевести исходные числа из десятичной системы счисления в двоично-десятичную;
- представить числа в форме с плавающей запятой;
- произвести перемножение чисел по алгоритму “Г” в дополнительных разрядах на два разряда одновременно;
- оценить погрешность вычисления после перевода результата в исходную систему счисления.
2. Алгоритм выполнения операций сложения и вычитания.
3. Структурную схему комбинированного устройства (сложение и умножение), содержащую узлы для действия над мантиссами и порядками, и определить время умножения с учетом временных задержек в комбинационных схемах.
4. Функциональные схемы основных узлов проектируемого сумматора-умножителя в заданном логическом базисе. Для этого провести:
- логический синтез комбинационного одноразрядного четверичного сумматора (ОЧС) на основе составленной таблицы истинности для суммы слагаемых с учетом переноса из младшего разряда, используя при этом алгоритм извлечения (Рота), и оценить эффективность минимизации;
- логический синтез одноразрядного комбинационного четверичного умножителя-сумматора (ОЧУС), путем минимизации переключательных функций по каждому выходу схемы. Минимизация выполняется с применением карт Карно-Вейча с последующей оценкой эффективности минимизации;
- логический синтез комбинационной схемы преобразователя множителя (ПМ);
- построить функциональную схему ОЧС на мультиплексорах;
- построить функциональную схему ПМ и ОЧУС в заданном базисе;
5. Определить время умножения на один разряд и на n
разрядов множителя.
6. Разработать алгоритм выполнения операции деления.
7. Функциональную схему делителя, представив его как управляющий автомат, для чего необходимо:
- построить граф связности автомата;
- разметить его для синтеза автомата Мура;
- построить таблицу переходов автомата;
- определить переключательные функции выходных сигналов и сигналов обратной связи;
- построить функциональную схему делителя на базе программируемой логической матрицы и заданных триггеров.
Исходные данные к курсовому проекту
В качестве исходных данных к курсовому проекту задается следующее:
1. Исходные операнды - десятичные числа с целой и дробной частью, над которыми производится операция умножения (36,39 & 53,25).
2. Алгоритм выполнения операции умножения Г.
3. Метод ускоренного умножения на базе которого строится умножитель:
- умножение закодированного двоично-четверичного множимого на 2 разряда двоичного множителя одновременно в дополнительных кодах;
Преобразование множителя в обоих случаях производится для исключения из процесса умножения диады множителя 11.
4. Двоичные коды четверичных цифр множимого для работы в двоично-четверичной системе счисления (представляется кодом: 04
- 00, 14
- 11, 24
- 01, 34
- 10)
. Множитель представляется обычным весомозначным кодом: 04
- 00, 14
- 01, 24
- 10, 34
- 11
.
5. Тип синтезируемого устройства умножения, определяемый основными структурными узлами, на базе которых строится умножитель:
- умножитель 2-го типа строится на базе ОЧУС, ОЧС и регистра результата.
6. Способ минимизации и логический базис для аппаратной реализации ОЧС и ОЧУС (функционально полный базис представлен функцией x1
+ x 2
:
Таблица 1. Таблица истинности:
| X1
|
X2 |
1 |
не 1 |
| 0 |
0 |
0 |
1 |
| 0 |
1 |
1 |
0 |
| 1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
0 |
ОЧС реализуется на мультиплексорах).
7. Алгоритм выполнения операции деления:
- деление с восстановлением остатков;
8. Класс синтезируемого микропрограммного автомата: Мура.
9. Логический базис для аппаратной реализации делителя, как управляющего автомата: ПЛМ и триггеры для организации цепи обратной связи (Т -триггеры).
Разработка алгоритма умножения
1. Перевод сомножителей из десятичной системы счисления в четверичную:
МНОЖИМОЕ
36 | 4
0,39 Мн4
=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 Мт4
= 311,1
52
13 | 4
4
Мт2/4
= 110101,01
1 12
3 1,00
1
2. Запишем сомножитель в форме с плавающей запятой в прямом коде:
Мн = 0,01110011010010 Рмн
= 0,0010 +03 закодирован по заданию
Мт = 0,11010101 Рмт
= 0,0011 +03 незакодирован по заданию
[Мт]д
= Мт = 0,31114
= 0,110101012/4
[Мт]дп
= 0,1010101012/4
Мн = 0,2101203
[-Мн]д
= 3,1232131
3. Умножение двух чисел с плавающей запятой на 2 разряда множителя одновременно в дополнительных кодах сводится к сложению порядков, формированию знака произведения, преобразованию разрядов множителя с целью исключения диады 11, и перемножению мантисс сомножителей.
Порядок произведения будет равен:
Рмн
= 0.0010+
03
Рмт
= 0.0011 03
Р = 0.1101 12
результат закодирован в соответствии с заданием на кодировку множимого.
Знак произведения определяется суммой по модулю два знаков сомножителей, т.е.:
зн Мн + зн Мт = 0 + 0 = 0.
Для умножения мантисс необходимо предварительно преобразовать множитель, чтобы исключить диаду 11(34
), заменив ее на триаду 101.
Перемножение мантисс по алгоритму «Г» приведено втаблице 2:
[Мт]дп
= 0,1010101012/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 с/с |
|
4. После окончания умножения необходимо оценить погрешность вычислений. Для этого полученное произведение (Мн*Мт4
=013210121133 РМн*Мт
= 6) приводится к нулевому порядку, а затем переводится в десятичную систему счисления:
Мн*Мт4
= 132101,21133 РМн*Мт
= 0;
Мн*Мт10
= 1937,5927734375.
Результат прямого перемножения операндов дает следующее значение:
Мн10
*Мт10
= 36,39 * 53,25 = 1937,7675.
Абсолютная погрешность:
D = 1937,7675 - 1937,5927734375 = 0,17473.
Относительная погрешность:
D 0,17473
d = = = 0,00009017 (d = 0,00901%)
Мн*Мт 1937,7675
Эта погрешность является суммарной, накопленной за счет приближенного перевода из 10 с/с в четверичную обоих сомножителей, а также за счет округления полученного результата произведения.
В случае отрицательного множимого:
[Мт]дп
= 0,1010101012/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 такта) заносятся в регистр множимого, а на управляющий вход ФДК F2
поступает «1». На выходах ФДК формируется дополнительный код первого слагаемого с учетом знака. Первое слагаемое без изменений должно быть записано в регистр результата, поэтому управляющие сигналы, поступающие на входы «h» всех ОЧУС, позволяют переписать на выходы ОЧУС разряды первого слагаемого без изменений. Если на вход «h» поступает «0», то ОЧУС перемножает разряды Мн и Мт и добавляет к полученному результату перенос из предыдущего ОЧУС.
Если устройство работает как умножитель, то множимое и множитель помещаются в соответствующие регистры, а на управляющий вход ФДК F2
поступает «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 ). В этом случае инициализируется управляющий вход F1
формирователя дополнительного кода (ФДК), и на выходах ФДК формируется двойной дополнительный код множимого (умножение на -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=x2Åx3 |
Преобразователь множителя.
Структурная схема устройства приведена на рисунке в приложении. Она содержит регистры: множимого (Рг Мн), множителя (Рг Мт), результата (Рг Рез), формирователи дополнительного кода (ФДК) , 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
| À1 |
À2 |
В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
td>
|
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 ОЧС.
| À1 |
À2 |
В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 ОЧС.
| À1 |
À2 |
В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
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.
| (ZE)
01x11 01111 O
x1011 O O
011x1 01111 O
1x011
1x10x
101xx
|
Тупиковые формы: 01x11, 011x1 & 1x10x, 101xx
Минимизированная переключательная функция для выхода переноса ОЧС Cmin
:
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.
|
Так как 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È(C0Z0)
| 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
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-триггеры.