1
Оглавление
Постановка задачи
Исходные данные к курсовому проекту
Разработка алгоритма умножения
Разработка структурной схемы устройства
Синтез преобразователя множителя
Логический синтез одноразрядного четверичного умножителя-сумматора
Логический синтез одноразрядного четверичного сумматора
Синтез МПА делителя
Постановка задачи
Курсовой проект предполагает синтез цифровых схем арифметических
устройств, выполняющих операции сложения, вычитания, умножения и деления
над числами, представленными в форме с плавающей запятой в двоичной и
двоично-четверичной системах счисления.
По исходным данным необходимо разработать:
1. Алгоритм выполнения операции умножения, для чего потребуется:
n перевести исходные числа из десятичной системы счисления в
двоично-десятичную;
n представить числа в форме с плавающей запятой;
n произвести перемножение чисел по алгоритму “Г” в дополнительных
разрядах на два разряда одновременно;
n оценить погрешность вычисления после перевода результата в исходную
систему счисления.
2. Алгоритм выполнения операций сложения и вычитания.
3. Структурную схему комбинированного устройства (сложение и
умножение), содержащую узлы для действия над мантиссами и порядками, и
определить время умножения с учетом временных задержек в комбинационных
схемах.
4. Функциональные схемы основных узлов проектируемого
сумматора-умножителя в заданном логическом базисе. Для этого провести:
n логический синтез комбинационного одноразрядного четверичного
сумматора (ОЧС) на основе составленной таблицы истинности для суммы
слагаемых с учетом переноса из младшего разряда, используя при этом
алгоритм извлечения (Рота), и оценить эффективность минимизации;
n логический синтез одноразрядного комбинационного четверичного
умножителя-сумматора (ОЧУС), путем минимизации переключательных функций
по каждому выходу схемы. Минимизация выполняется с применением карт
Карно-Вейча с последующей оценкой эффективности минимизации;
n логический синтез комбинационной схемы преобразователя множителя (ПМ);
n построить функциональную схему ОЧС на мультиплексорах;
n построить функциональную схему ПМ и ОЧУС в заданном базисе;
5. Определить время умножения на один разряд и на n разрядов множителя.
6. Разработать алгоритм выполнения операции деления.
7. Функциональную схему делителя, представив его как управляющий
автомат, для чего необходимо:
n построить граф связности автомата;
n разметить его для синтеза автомата Мура;
n построить таблицу переходов автомата;
n определить переключательные функции выходных сигналов и сигналов
обратной связи;
n построить функциональную схему делителя на базе программируемой
логической матрицы и заданных триггеров.
Исходные данные к курсовому проекту
В качестве исходных данных к курсовому проекту задается следующее:
1. Исходные операнды – десятичные числа с целой и дробной частью, над
которыми производится операция умножения (36,39 & 53,25).
2. Алгоритм выполнения операции умножения Г.
3. Метод ускоренного умножения на базе которого строится умножитель:
n умножение закодированного двоично-четверичного множимого на 2 разряда
двоичного множителя одновременно в дополнительных кодах;
Преобразование множителя в обоих случаях производится для исключения из
процесса умножения диады множителя 11.
4. Двоичные коды четверичных цифр множимого для работы в
двоично-четверичной системе счисления (представляется кодом: 04 – 00, 14
– 11, 24 – 01, 34 – 10). Множитель представляется обычным весомозначным
кодом: 04 – 00, 14 – 01, 24 – 10, 34 – 11.
5. Тип синтезируемого устройства умножения, определяемый основными
структурными узлами, на базе которых строится умножитель:
n умножитель 2-го типа строится на базе ОЧУС, ОЧС и регистра результата.
6. Способ минимизации и логический базис для аппаратной реализации ОЧС
и ОЧУС (функционально полный базис представлен функцией x1 + x 2 :
Таблица 1. Таблица истинности:
X1X21не 10001011010101110
ОЧС реализуется на мультиплексорах).
7. Алгоритм выполнения операции деления:
n деление с восстановлением остатков;
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.0000000000000.000000000000+00.0000000000000.02101203
0000+Мн>>10.0210120300003.331232131000-Мн>>210.0123102210000.00021012030
0+Мн>>310.0131210013000.000021012030+Мн>>40.0132020133300.000002101203+М
н>>50.013210121133Рез. В доп коде0.013210121133Рез. В пр.
коде132101,211331937,592773437510 с/с
4. После окончания умножения необходимо оценить погрешность вычислений.
Для этого полученное произведение (Мн*Мт4=013210121133 РМн*Мт = 6)
приводится к нулевому порядку, а затем переводится в десятичную систему
счисления:
Мн*Мт4 = 132101,21133 РМн*Мт = 0;
Мн*Мт10 = 1937,5927734375.
Результат прямого перемножения операндов дает следующее значение:
Мн10*Мт10 = 36,39 * 53,25 = 1937,7675.
Абсолютная погрешность:
= 1937,7675 – 1937,5927734375 = 0,17473.
Относительная погрешность:
0,17473
d = = = 0,00009017 (d = 0,00901%)
Мн*Мт 1937,7675
Эта погрешность является суммарной, накопленной за счет приближенного
перевода из 10 с/с в четверичную обоих сомножителей, а также за счет
округления полученного результата произведения.
В случае отрицательного множимого:
[Мт]дп = 0,1010101012/4
Мн = – 0,2101203
[Мн]д = 3,1232131
[-Мн]д = 0,2101203
Четверичная с/сЗНАКРЕГИСТР
РЕЗУЛЬТАТАДЕЙСТВИЯ0.0000000000000.000000000000+00.0000000000003.31232131
0000
+Мн>>13.3123213100000.002101203000-Мн>>23.3210231130003.333123213100
+Мн>>310.3202123321003.333312321310 +Мн>>410.3201313200103.333331232131
+Мн>>510.320123212201Рез. В доп коде1.
3 – 4=1013210121133Рез. В пр. коде132101,211331937,592773437510 с/с
Разработка структурной схемы устройства
Структурная схема строится на основе следующих блоков
· Многоразрядный регистр сдвига
сдвиг
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. Таблица истинности преобразователя множителя.
D1D2D3P1P2F000000001010010010011100100101101011110011111000
Исходя из выше изложенной таблицы синтезируется схема.
_ _ _ _ _ _ _ _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У2h РQ1Q2В
четверичной с/с0000000000*0+0=00000001000Выход – код
«00»0000100000*1+0=00000011000Выход – код
«00»0001000000*2+0=00000101000Выход – код
«00»000110ХХХ0*3+0=00*000111ХХХВыход – код
«00»*0010000002*0+0=00001001001Выход – код
«02»0010100012*1+0=02001011001Выход – код
«02»0011001002*2+0=10001101001Выход – код
«02»001110ХХХ2*3+0=12*001111ХХХВыход – код
«02»*0100000003*0+0=00010001010Выход – код
«03»0100100103*1+0=03010011010Выход – код «03»0101001013*2+0=12
010101010Выход – код «03»010110ХХХ3*3+0=21*010111ХХХВыход – код
«03»*0110000001*0+0=00011001011Выход – код
«01»0110100111*1+0=01011011011Выход – код
«01»0111000011*2+0=02011101011Выход – код
«01»011110ХХХ1*3+0=03*011111ХХХВыход – код
«01»*1000000110*0+1=01100001000Выход – код
«00»1000100110*1+1=01100011000Выход – код
«00»1001000110*2+1=01100101000Выход – код
«00»100110ХХХ0*3+1=01*100111ХХХВыход – код
«00»*1010000112*0+1=01101001001Выход – код
«02»1010100102*1+1=03101011001Выход – код
«02»1011001112*2+1=11101101001Выход – код
«02»101110ХХХ2*3+1=13*101111ХХХВыход – код
«02»*1100000113*0+1=01110001010Выход – код
«03»1100101003*1+1=10110011010Выход – код
«03»1101001103*2+1=13110101010Выход – код
«03»110110ХХХ3*3+1=12*110111ХХХВыход – код
«03»*1110000111*0+1=01111001011Выход – код
«01»1110100011*1+1=02111011011Выход – код
«01»1111000101*2+1=03111101011Выход – код
«01»111110ХХХ1*3+1=10*111111ХХХВыход – код «01»*
В таблице выделено 16 безразличных наборов, т.к. на входы ОЧУС из
разрядов множителя не может поступить код 11.
Таблица 6. Шестнадцать безразличных наборов для ОЧУС.
P1X1X2Y1Y2H0001100001110011100011110101100101110111100111111001101001111
01110101111110110110111111110111111
Таблица 7. Единичные наборы для выхода Q1 ОЧУС:
P1X1X2Y1Y2h0100010100100100110101010110010110100110110111011000001000101
001001010001010101011001100001100011100111101001101011110001110011110111
11100111101
Таблица 8. Карта Карно-Вейча для единичных наборов выхода Q1 ОЧУС:
1*1*111*11*1111*11*111*1*111*1*****11*1*
Q1 = X1 H + P1 X1 Y2 + P1 Y2 H + P1 X1 H =
= X1(H + P1 Y2) + P1 H(Y2 X1)
Таблица 9. Единичные наборы для выхода Q2 ОЧУС:
P1X1X2Y1Y2h0010010010100010110011010101000110010110100110110111000011011
000001000101001001010001010011010111011001111011100001110001110011110101
11011111101
Таблица 10. Карта Карно-Вейча для нулевых наборов выхода Q2 ОЧУС:
1*1*1111*11*11***1*11*1*1**11*11*11*1*11
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:
P1X1X2Y1Y2h001100010100101100110010110100
Таблица 12. Карта Карно-Вейча для единичных наборов выхода переноса ОЧУС
P:
1*11********11*******
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. Коэфициент минимизации.
Цена исходного покрытияЦена минимального покрытияКоэфицент
минимизацииQ11541510,27Q215432 4,81P23514 2,5
Логический синтез одноразрядного четверичного сумматора
ОЧС – это комбинационное устройство, имеющее 5 входов (2 разряда одного
слагаемого, 2 разряда второго слагаемого и вход переноса) и 3 выхода.
Принцип работы ОЧС описывается с помощью таблицы истинности (табл.3).
Разряды обоих слагаемых закодированы: 0 – 00; 1 – 11; 2 – 01; 3 – 10.
Таблица истинности функционирования ОЧС строится для пяти переменных,
четыре из которых (А1, А2, В1, В2) являются выходами ОЧУС, а пятая –
межразрядный перенос из ОЧС смежного старшего разряда устройства
умножения. Четверичная цифра суммы как диада S1S2 в таблице истинности
образуется с учётом принятого кодирования четверичных цифр.
Табл. 14
A1A2В1В2p P S1 S2в четверичной
с/с000000000+0+0=00000010110+0+1=01000100010+2+0=02000110100+2+1=0300100
0100+3+0=03001011000+3+1=10001100110+1+0=01001110010+1+1=02010000012+0+0
=02010010102+0+1=03010101002+2+0=10010111112+2+1=11011001112+3+0=1101101
1012+3+1=12011100102+1+0=03011111002+1+1=10100000103+0+0=03100011003+0+1
=10100101113+2+0=11100111013+2+1=12101001013+3+0=12101011103+3+1=1310110
1003+1+0=10101111113+1+1=11110000111+0+0=01110010011+0+1=02110100101+2+0
=03110111001+2+1=10111001001+3+0=10111011111+3+1=11111100011+1+0=0211111
0101+1+1=03
Безразличные наборы в таблице истинности отсутствуют т.к. со старших
выходов ОЧУС могут прийти коды 0, 1, 2 и 3.
Таблица 15. Единичные наборы для выхода переноса P ОЧС.
A1A2В1В2
p00101010100101101100011010111110001100101001110100101011011010111110111
110011101
Таблица 16. Единичные наборы для выхода S1 ОЧС.
A1A2В1В2
p00001000110010000110010010101101100011101000010010101011011111000110101
110111111
Таблица 17. Единичные наборы для выхода S2 ОЧС.
A1A2В1В2p000010001000110001110100001011011000110110010100111010010111110
00110011110111110
Алгоритм Рота для выхода переноса ОЧС
Отыскание множества L-экстремалей
Z0=; C0=L;
Множество С0: 11101; 00101; 01010; 01011; 01100; 01101; 01111; 10001;
10010; 10011; 10100; 10101; 10110; 10111; 11011.
C0*C01110100101010100101101100011010111110001100101001110100101011011010
111110111110100101yy10101010y1yyy0yyyy01011y1yy10yyy10101x01100y110y0y10
y01yy001yyy01101x11010x10101yyy01yy10110x01111y11y10y1y101y1y01x11011yy0
11x1100011yy01y0y01yy0yyyy0y1yyy0yyyy01yyyy1100101yyyyy0yyyyy010yy01yyyy
y0yyyyyyyy1y100yy100111yyy1y0yy1yy01yyy011yyyyyyyyy1yyy11100x11001x10100
1y10yy010yyyyy0yyyyyyy100yy10yyy1yy10y0y10yy010yyy101011x101x0101yyyyyyy
yy1yy10yyy101yy1y110x0110yyy10yy11010x101101y1yyy01yyyyy10yyy1yyy1y0yy1y
yyy11y10yyy10x1010y1y101x0101yy101111y1y1y01y1yyy1yyyy11yy1yyyy1y1yy1111
0yy110y1y10x11101yy101x11011x1101111yy1yyyy1y101yx1011y1yyyy1yy1y1y111y0
y11y01y1x0111yyyy1yyy11yy1y1yy11111001110xyy10yy1yy0y1yyyx1100y110yy11yy
1yy0y1yyy01yyyy1x1001y10y1y1y01y1yy11yyy
Кубы, образовавшиеся в этой таблице, образуют множество A1. Множество C1
получаем по формуле: C1=A1(C0-Z0)
Множество C1: x1101; 1×101; 1110x; 0x101; x0101; 0101x; 01×11; x1011;
0110x; x1100; 011×1; 100×1; 10×01; 1001x; 10×10; 10×11; 1×011; 1010x;
101×0; 1×100; 101×1; 1011x.
C1*A1x11011x1011110x0x101x01010101x01x11x10110110xx1100011x1100x110x0110
01x10x1010x11x0111010x101x01x100101x1x11011x101111011110x11101111010x101
01101xx101x1101x0101xx101101011x101001010101x01yy1y1yy1y1yyx01yy10yyy101
x11011x1y11y1y11y1011x10y1y101011x1011x1yy111yy111yy101yy1xyyy1010110101
10110x01101x1101x110x011010x10101yyx011x101yy1x1100x110x1110x111000110xx
y10y01yy0011yyx1yyy01100011x101101x1101x1101011010x10101x110111101x11011
010110x100x11yy0110x011yy01y0y0110x01yy011yy0111x011yyy011yy0yyyyx110x01
1x101101011x101x010110101yy0y1yyxy11y0y1yy1011y10yyy101100011001x1yyy110
yy11yyyxy0yy110yy1yy01xyy0111x011yyyyx1yyy0yyy1110011100x110x101y1yy101y
y1y1y0y01yy101yyyy010yyx1y1y01yyy1y01y1y0yy11y1001x10xyy1001010x111y1y11
01x11y1y1y01y1101x1yy011yyx111x011yy1y11y1yyyy1111001110xx11001110x1x1x0
1111yy11xyy111yy1yxyy110yy1x1011x101111011y1yy111yyyy1y1110011100x110011
1001x100111010x1x101101011x10xx010110101yyyyxyy1y11yyy1yy10x1x100yy10110
x011010110yyx101x0101x110yy1101x01y10y1010x1x100y010y1010xyyy10yy11y1yy1
yyy1001x100yy1xy10yxy1010x10x10101101011x10y1y101001x1001110x1x10x11100y
x10y1010xy1yy0y11yy11yyyx110011100y110y10y0y1010x10yy0101x0101yy1xyyy101
0010100101x11x101101011x101x010110101yyy11yy1111yy11yy1011y10yyy1x110xx1
1010110x111011x1011110x1110101101xx1010x1011x1y1y1101x11y1yxy01y1101x1yy
y1xyy1111yy11yy1yx1y1y0yy11110x11101x110x1x101101011110x11101xx10110101x
010111Множество C2: xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx.
*xx101x110x1x10x10xx110x1xxx101x110xx11011x10x1x1011110x10xx1101011x1011
010110x1x101x11y1yx101xx10x11101xx101011x10x1010x101x11011x
Множество С3 – пустое (склеивание не дало новых кубов более высокой
размерности).
Множество простых имплекант Z: 0101x; 01×11; x1011; 011×1; 1×011; xx101;
x110x; 1x10x; 10xx1; 10x1x; 101xx.
Отбросим те кубы из множества Z, которые покрываются другими.
Z#z 0101x 01×11 x1011 011×1 1×011 xx101 x110x 1x10x 10xx1 10x1x 101xx
0101x _ 01111 11011 011×1 1×011 xx101 x110x 1x10x 10xx1 10x1x 101xx
01×11 01010 _ 11011 01101 1×011 xx101 x110x 1x10x 10xx1 10x1x 101xx
x1011 01010 01111 _ 01101 10011 xx101 x110x 1x10x 10xx1 10x1x 101xx
011×1 01010 11011 _ 10011 1×101 1110x 1x10x 10xx1 10x1x 101xx
x0101 x1100
1×011 01010 01101 _ 1×101 1110x 1x10x 101×1 1011x 101xx
x0101 x1100 10×01 10×10
xx101 01010 10011 _ 11100 1×100 10111 1011x 1011x
x1100 10001 10×10 101×0
x110x 01010 10011 10101 _ 10100 10111 1011x 1011x
x0101 10001 10×10 101×0
1x10x 01010 10011 _ 10111 1011x 1011x
00101 01100 10001 10×10 10110
10xx1 01010 00101 01100 10100 _ 10110 10110
10×10
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.
(ZE)(L#E)01111 10100
01×11 01111 O
x1011 O O
011×1 01111 O
1×011 O O
1x10x O 10100
101xx O 10100
Тупиковые формы: 01×11, 011×1 & 1x10x, 101xx
Минимизированная переключательная функция для выхода переноса ОЧС Cmin:
0101x; xx101; x110x; 10xx1; 10x1x; 01×11; 101xx.
Алгоритм Рота для выхода S1 ОЧС
C0=L; Z0=0;
Множество С0: 00001; 00011; 00100; 00110; 01001; 01011; 01100; 01110;
10000
10010; 10101; 10111; 11000; 11010; 11101
C0*C00000100011001000011001001010110110001110100001001010101101111100011
010111010000100011000x10010000y0y00yyy0011000yyy00y1y001x0010010x0010y0y
10yy0y0yyyy010110y0y10x0110yyyy0yy1y010x1011000yy0y0yyyy0x1000y1y001y0y0
1yyy011100yyyy0yy1y0y1y00x11001yyy01y1y011x010000y000yy00yyy0y00y0yy0yy0
0yyy0yyyyy00yyyy010010y00yyy001yy0yy0y0y10yy0yyyy01yyyyy0yyy10100x010101
y0y01y0yy1y010yy01yyyyy01yyyy1yy10yyy1yy10y0y10yyy10111y0yy1y0y11y01yyy0
11yyyyy1yyy11yy1yyyy11y10yyy10y1y101x111000yy00yyy0yyyyy00yyyy0y100yy10y
yy1y00y1yy01x0001y0y01yy0y1yyyy11010yy0yyyy01yyyyy0yyy10y10yyy101yy1yy0y
1y101y0y01x0101yyyy1yy1y110x011101yyy01yyyy1yy10yyy1yyy1y01y1yy1y110yy11
yy1yy0y1yyyy1x1011y1y111y0y11yyy11111yyyy1yyy11yy1yyyy11yy1yy1y1y11y11yy
y111y1yyyy1yy1y1y1y11x11111yyy11y1y111x1
C1=A1(C0-Z0)
Множество C1: 000×1; 0x001; 0x011; 001×0; 0x100; 0x110; 010×1; 011×0;
100×0; 1×000; 1×010; 101×1; 1×101; 1×111; 110×0; 111×1.
C1*A1000x10x0010x011001x00x1000x110010x1011x0100x01x0001x010101x11x1011x
111110x0000x10x001000010x011000110x0x1001x000yxy00y0y00y1y0x10000y0y0xy0
y0xyyy001000x11000y1y0xyyy0xy1y001100x1x0010x10x0x101001010110yyxy01y0y0
1y1y011x00yyxy01y0y01y1y0x1x0011000111001yxy100x0y00xyy000yy001yy0yx0y0y
00y0y10yy0xyyyyx01x000y000yyx00yyx0yyy0y00yxy00yxyy0y100yy1y00100001x010
y001yyx0yyyx01yy0y10yxyy0yxy10y101yy1y10100101x0x0101x1y0yx1y0y01y0y11y0
1xyy010yy011yyyyx1yy1xy10yxy10y0y10y1y1x101y0y01yxy01yxyy1y010yyx10yyx1y
yy1y01y110y10y0y1xy0y1xyyy101011x111y0y11yxyy1yxy11y011yyx1yyyx11yy1y11y
111y10y1y1xyyy1xy1y101111x1x1110x0yy0xyy100yy101yyyyx0y1y00y1y10y10xyy1y
x01x0x011000110101yyxy11y0y11y1y111x1yyyx1y1y01y1y11yy1xyy110yy111yy1yx1
y11xy1yyxy11y0y11y1y1x1x1111011111111yxy
Множество C2: 0x0x1; 0x1x0; 1x0x0; 1x1x1.
C2*A20x0x10x1x01x0x00x0x10x1x00xyxy1x0x0yx0xyyxyx01x1x1yxyx1yx1xy1xyxy
Множество С3 – пустое.
Множество простых имплекант Z: 0x0x1; 0x1x0 1x0x0; 1x1x1.
Z#Z0x0x10x1x01x0x01x1x10x0x1-0x1x01x0x01x1x10x1x00x0x1-1x0x01x1x11x0x00x
0x10x1x0-1x1x11x1x10x0x10x1x01x0x0–0x0x10x1x01x0x01x1x1
С помощью операции пересечения находим 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-экстремали, и только они входят в 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*C00000100010001100011101000010110110001101100101001110100101111100011
001111010000100010000yy0011000yyy00x100011100yy100y1y0011x010000y00y0y0y
00yyy00yyyy010110y0y10y01y0yy1y0yy11010yy011000yy0y0yyy00y1y00y1yy01x000
1yyy011010yy010yyyy0y1yy0y1y101y0y01yy10110x10010y00yyx0010y0y10y0y1yyy0
y0yy01yyyyy0yyyyy10011y00y1y001yy0y1yy0y11yy0yyyy011yyyyyyyyy11001x10100
y0y0yy0yy0y01y0y01yyyyy00yyyyyyy100yy10y10yy010yyy10111y0yy1y0y1yy011yx0
111yyyyyyyy11yy1yyyy1y110y1y10x11101yy11000yy00yyy0y0yyyy0yyyyyx1000y10y
yy1y00y1y0y1y0y01y0yy1yy001yyyy11001yy001yy0yyyyyyyyyyy1y100yy10y1y1y0yy
1y011y0yy1y0y11yy0y1yyy11100x11101yyy01yyyyyyy1yyyy1y1y1y0yy1yy1y110yx11
011yyyy1yyy11y10y1y1y111y0y11x0111110yyyyyyyy10yy110yy11yy1yy0y1y1yy11y0
y11yy1yy101yy1y1y1y01y11y11yy011yyy111yy
Множество C1:
00×10 x0010 0011x x0111 01×00 x1000 0110x x1101 1001x 10×11 1100x 11×01
C1=A1(C0Z0)
C1*A100x10x00100011xx011101x00x10000110xx11011001x10x111100x00x10x001000
0100011x0011000x10x01110011xx0y1y0011101x000yxy00y0y00y1y00y1yyx10000y0y
0xy0y00yyy0xyyyy010000110x0y1y00yyy00y1yx0y1y10110001x00x11010y1yyxyyyy0
y1y1xy1y10110xx1y0y011011001xx001010010y0y1x10x11yy0y01y0y0yyyyx1yyy110x
11y0x1y1001xx011110111yyxyy1y0yyyy1y11y1y1100111100xyy0y01y0y0yyyyx1yyy1
x100011000y1y0x11x011y0yx1y0y111x01yyxyy1y0yyyy1y11y1y1y1x0y1100xx110111
1011y0y11yxy111001
Множество С2 – пустое
Множество простых имплекант Z: 00001; 01011; 10100; 11110; 00×10; x0010;
0011x; x0111; 01×00; x1000; 0110x; x1101; 1001x; 10×11; 1100x; 11×01.
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
00×10 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
01×00 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
10×11 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
11×01 O O O O O O O O O O 11001
11101
Тупиковые формы: 00×10, x0111, 01×00, x1101, 1001x, 1100x
Cmin=00001; 01011 10100; 11110, 00×10, x0111, 01×00, x1101, 1001x, 1100x
Эффективность минимизации определяется коэфицентом минимизации. Он
расчитывается по следующей формуле:
Цена исходного покрытия
Коэф.=—————————————–
Цена минимального покрытия
Таблица 13. Коэфициент минимизации.
Цена исходного покрытияЦена минимального покрытияКоэфицент
минимизацииQ184614Q284352,4P284214
Синтез МПА делителя
Автомат должен управлять делением с восстановления остатка. Блок-схема
этого алгоритма приведена ниже:
Y0 – суммирование делимого и двойного дополнительного кода делителя.;
Y1 – занесение нуля в регистр частного, восстановление остатка
(суммирование делимого и делителя);
Y2 – занесение единицы в регистр частного;
Y3 – сдвиг регистра суммы и частного влего, наращивание точности
частного;
X1 – проверка знакового разряда регистра суммы (0 – положительное, 1 –
отрицательное);
X2 – проверка достижения точности вычисления;
По условию задачи делитель необходимо синтезировать в виде управляющего
автомата Мура. Разметка ГСА в этом случае происходит по следующему
алгоритму:
1. Меткой a1 отмечаются первая и последняя вершины.
2. Метками a2..am отмечаются все операторные вершины.
По отмеченной ГСА строится таблица переходов:
amK(am)asF(am,as)
K(as)X(am,as)Y(am,as)A1000A2001001—-A2001A3011010X1Y0A2001A4010011X1Y0
A3010A5110100–Y1A4011A5111100–Y2A5100A2101001X2Y3A5100A1100000X2Y3
По построенной таблице сформируем таблицу истинности для настройки ПЛМ:
X1X2T1T2T3Y0Y1Y2Y3D1D2D3–00000000010-00110000101-0011000011–0100100000
–0110010001-01000001111-11000001100
По полученной таблице построим автомат, в качестве памяти используя
T-триггеры.
picscalex1000100090000032a0200000200a20100000000a201000026060f003a03574d
464301000000000001004e83000000000100000018030000000000001803000001000000
6c0000000000000000000000350000006f00000000000000000000002933000084280000
20454d460000010018030000120000000200000000000000000000000000000070120000
781a0000c80000001f010000000000000000000000000000850c03008260040016000000
0c000000180000000a0000001000000000000000000000000900000010000000150c0000
92090000250000000c0000000e000080250000000c0000000e0000805200000070010000
01000000a4ffffff00000000000000000000000090010000000000cc0440002243006100
6c0069006200720069000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000001100dc5f110010000000
40631100c060110052516032406311003860110010000000a86111002463110024516032
40631100386011002000000049642f31386011004063110020000000ffffffff9c1ed800
d0642f31ffffffffffffffffffff01800fff0180ffffffff000000000008000000080000
d4fb8c0501000000000000005802000025000000372e9001cc00020f0502020204030204
ef0200a07b20004000000000000000009f00000000000000430061006c00690062007200
00000000bb01917c00611100dee32e31e88d0832606411006c6011009c38273106000000
01000000a8601100a8601100e878253106000000d06011009c1ed8006476000800000000
250000000c00000001000000250000000c00000001000000250000000c00000001000000
120000000c00000001000000180000000c00000000000002540000005400000000000000
00000000350000006f00000001000000dd97874085898740000000005700000001000000
4c000000040000000000000000000000160c000092090000500000002000190036000000
46000000280000001c0000004744494302000000ffffffffffffffff170c000093090000
000000004600000014000000080000004744494303000000250000000c0000000e000080
250000000c0000000e0000800e0000001400000000000000100000001400000004000000
03010800050000000b0200000000050000000c029f010c02040000002e0118001c000000
fb020300010000000000bc02000000cc0102022253797374656d00000000000000000000
00000000000000000000000000000000040000002d010000040000002d0100001c000000
fb02f0ff0000000000009001000000cc0440002243616c69627269000000000000000000
00000000000000000000000000000000040000002d010100040000002d01010004000000
2d0101000400000002010100050000000902000000020d000000320a0f00000001000400
000000000c029f0120000900040000002d010000040000002d010000030000000000
Нашли опечатку? Выделите и нажмите CTRL+Enter
