Министерствообразования Российской ФедерацииТомскийполитехнический университет
Факультетавтоматики и вычислительной техникиКафедравычислительнойтехники
Курсоваяработа
по дисциплине“Теория автоматов”
на тему:«Синтез и анализ логической схемы при кубическом задании булевой функции»
Томск 2009
СОДЕРЖАНИЕ
Введение
1. Нахождение минимального покрытия
2. Построение факторизованного покрытия
3. Составление логической схемы наоснове данного базиса логических элементов
4. Нахождение по пи-алгоритму Ротаединичного покрытия
5. Синтез контролирующего теста.Контроль схемы тестом
Заключение
Литература
ВВЕДЕНИЕ
Аппарат алгебры логики широко применяется в теорииЦВМ, в частности для решения задач анализа и синтеза схем. При решении задачисинтеза исходное логическое выражение, описывающее некоторую логическуюфункцию, преобразуется и упрощается так, чтобы каждый член полученногоэквивалентного логического выражения мог быть представлен простой схемой. Такимобразом, при синтезе вычислительных и управляющих схем составляетсяматематическое описание задачи в виде формул алгебры логики. Затем производитсяминимизация исходной формулы и из числа эквивалентных логических схемвыбирается та, которая допускает наиболее простую реализацию.
В данной курсовой работе стоит задача синтеза схемы,реализующей функцию, заданную кубическим комплексом к(f).В табл. 1 приведено исходное покрытие из 8 кубов. Логическую схему следуетпостроить в универсальном базисе элементов ИЛИ-НЕ, который характеризуетсякоэффициентом объединения по входу к(вх)=4 и коэффициентом разветвления повыходу к(р)=2. Стоимость покрытия равна 48.
Таблица 1Обозначение куба Покрытие Размерность куба a 1011X10 6 b 1X1XX11 4 c 1011X11 6 d XX1X1X0 3 e 0X11111 6 f 00X0XX0 4 g 0X00101 6 h 10X00X0 5
Порядок выполнения работы можно определить следующимобразом:
1). Нахождение минимального покрытия;
2). Построение факторизованного покрытия;
3). Составление логической схемы на основе данногобазиса логических элементов;
4). Нахождение по пи-алгоритму Рота единичногопокрытия;
5). Построение контролирующего теста;
6). Проверка логической схемы контролирующим тестом.
1. НАХОЖДЕНИЕМИНИМАЛЬНОГО ПОКРЫТИЯ
В первую очередь необходимо найти минимальное всмысле Кванта покрытие. Минимальное покрытие булевой функции ищется в дваэтапа:
1).получение минимального множества Zпростых импликант;
2).выделение L-экстремалейна множестве Z.
Для выполнения этих этапов используются операции*-произведения, #-вычитания кубов.
При выполнении операции *-произведения одного кубана другой получается новый куб, противоположные грани которого лежат в исходныхкубах. Этот новый куб может стать простой импликантой исходного покрытия. Надоиметь в виду, что куб является простой импликантой исходного покрытия, если онне составляет грань никакого другого комплекса К или того куба, которыйполучился при произведении в процессе нахождения простых импликант. Этоозначает, что простые импликанты при *-произведении не дают новых кубов, невходящих в предыдущие кубы.
При нахождении простых импликант выполняются всепопарные произведения с учетом того, что произведение куба самого на себяприводит к кубу, участвующему в произведении; что произведение первого куба навторой равно произведению второго куба на первый.
Операция *-произведения двух кубов а=а1а2…аi…anи b=b1b2…bi…bnопределяется на основе табл. 2.
Таблица 2
ai * bi
ai 1 X
bi Y 1 Y 1 1 X 1 X
Если значение Yполучается только в одной координате, то произведение кубов aи b дает так называемый вновьобразованный куб, в котором величина Yзаменяется на X. Если же имеется болееодной координаты Y, то звездчатоепроизведение дает 0.
Процесс нахождения множества простых импликантявляется циклическим. В каждом цикле вначале удаляются те кубы исходногопокрытия, которые являются гранями других кубов этого покрытия. Далее удаляютсякубы исходного покрытия, являющиеся гранями кубов покрытия. Должны быть удаленыполученные при *-произведении кубы, являющиеся гранями кубов покрытия. И наконец,удаляются полученные кубы с размерностью, на единицу меньшей номера цикла.Оставшиеся в таблице кубы передаются на следующий цикл *-произведения. Циклывыполняются до тех пор, пока перестанут появляться вновь образованные кубы.Процесс нахождения множества простых импликант для 35-го варианта приведен втабл. 3,4,5,6. Куб «с» не используется при нахождении данного множества, т.к.он входит в куб «b».
1 цикл нахождения множества простых импликант Таблица3 1011X10 1X1XX11 XX1X1X0 0X11111 00X0XX0 0X00101 1011X10 - 1X1XX11 1011X1X - XX1X1X0 1011110 1X1X11X - 0X11111 Æ XX11111 0X1111X - 00X0XX0 Æ Æ 00101X0 Æ - 0X00101 Æ Æ Æ Æ 000010X - 10X00X0 101X010 101001X 1010XX0 Æ X0X00X0 Æ
2 цикл нахождения множества простых импликант Таблица4 1Х1ХX11 XX1X1X0 00X0XX0 0X00101 1011X1X 101X010 1X1X11X XX11111 101001X 0X1111X 1010XX0 000010X 1X1XX11 - XX1X1X0 - 00X0XX0 - 0X00101 - 1011X1X 1011X11 101111X Æ Æ - 101X010 101X01X 101XX10 Y010010 Æ 1011010 - 1X1X11X 1X1X111 1X1X110 Y010110 Æ 101111X 101XY10 - XX11111 1X11111 XX1111X Æ Æ 1011111 Æ 1X11111 - 101001X 1010011 1010Y10 Y010010 Æ 101X01X 1010010 1010Y1X Æ - 0X1111X XX11111 0X11110 001Y110 Æ X01111X Æ YX1111X 0X11111 Æ - 1010XX0 1010X1X 10101X0 X010XX0 Æ 101XX10 1010010 1010110 Æ 1010010 Æ - 000010X Æ 00Y0100 0000100 0000101 Æ Æ Æ Æ Æ Æ Æ - X0X00X0 101001X X010XX0 00X00X0 0000Y01 101Y010 1010010 1010Y10 Æ 1010010 Æ 10100X0 0000Y00 3 цикл нахождения множества простыхимпликант Таблица 5 1X1XX11 XX1X1X0 00X0XX0 0X00101 1011X1X 1X1X11X 000010X X0X00X0 101X01X 1010X1X 101XX10 XX1111X 1X1XX11 - XX1X1X0 - 00X0XX0 - 0X00101 - 1011X1X - 1X1X11X - 000010X - X0X00X0 - 101X01X 101X011 101XX10 X010010 Æ 101101X 101XX1X Æ 1010010 - 1010X1X 1010X11 1010110 X010X10 Æ 101XX1X 101011X Æ 1010010 101001X - 101XX10 101XX1X 101X110 X010X10 Æ 1011X10 101X110 Æ 1010010 101X010 1010X10 - XX1111X 1011111 XX11110 001X110 Æ 101111X 1X1111X Æ Æ 1011X1X 101X11X 1011110 - X010XX0 1010X1X X0101X0 0010XX0 Æ 101XX10 1010110 00X0100 X0100X0 1010010 1010X10 1010X10 X01X110
4 цикл нахождениямножества простых импликант Таблица 6 1X1XX11 XX1X1X0 00X0XX0 0X00101 000010X X0X00X0 XX1111X X010XX0 101XX1X 1X1XX11 - XX1X1X0 - 00X0XX0 - 0X00101 - 000010X - X0X00X0 - XX1111X - X010XX0 - 101XX1X 101XX11 101X110 X010X10 Æ Æ 1010010 101111X 1010X10 - 1X1X11X 1X1X111 1X1X110 X010110 Æ Æ 1010X10 1X1111X 1010110 101X11X
В таблицах 3, 4, 5 и 6опущены те *-произведения, которые были рассмотрены раньше. Множество простыхимпликант Z выглядит следующим образом:
Z={ 1X1XX11,XX1X1X0, 00X0XX0, 0X00101, 000010X, X0X00X0, XX1111X, X010XX0, 101XX1X,1X1X11X}.
Стоимость данного покрытия составляет 53, что на 5больше стоимости исходного покрытия.
После нахождениямножества Z в нем необходимо выделить такое подмножество,которое покрывало бы все вершины из комплекса L и имело бы минимальную стоимость по Квайну. В основе лежитпонятие L-экстремали, то есть куба Zi, содержащего в себе одну или нескольковершин из комплекса L (L=C), которой нет ни в одной другой простой импликанте измножества Z.
Куб Ziявляется L-экстремалью, если для него выполняется следующее соотношение:
[ Zi# ( Z — Zi)] Ç L ¹ Æ,
где # — знак операциивычитания кубов.
Операция вычитания,например, из куба а куба bслужит для удаления их общей части, т.е. их пересечения, из куба а. Этаоперация определяется следующим образом:Координатное вычитание кубов ( ai# bi) Таблица 7
ai # bi
ai 1 X
bi Z Y 1 1 Y Z X Z Z Z
Операция вычитания изкуба а куба b определяется следующим образом:
/>a, при наличии Y,
a # b = Æ, если ai# bi=Z,
È ( a1a2…ai-1aiai+1…an),
где ai= 0 или 1, объединение берется повсем таким ai.
Процесс выделения L-экстремали является циклическим, накаждом цикле очередная простая импликанта вычитается из предыдущей разности.Процессы вычитания и пересечения для полученных выше простых импликант отраженыв табл. 8.Выделение L-экстремалей Таблица 8
Z1
1X1XX11
Z2
XX1X1X0
Z3
00X0XX0
Z4
0X00101
Z5
000010X
Z6
X0X00X0
Z7
XX1111X
Z8
X010XX0
Z9
101XX1X
Z10
1X1X11X 1 2 3 4 5 6 7 8 9 10 11 12
Z1 1X1XX11 -
0ZZZZ0Y
XX1X1X0
YZ0ZZ0Y
00X0XX0
YZYZZYZ
0X00101
YZYZZY0
000010X
0Z0ZZ0Y
X0X00X0
0ZZZZZZ
0X1111X
0ZZZZ0Y
X010XX0
ZZZZZZ0
101XX10
ZZZZZZ0
1X1X110
Z2 XX1X1X0
ZZZZ0ZY
1X1XX11 -
ZZ0Z0ZZ
0000XX0
00X00X0
ZZYZZZY
0X00101
ZZYZZZ1
000010X
ZZ0ZYZZ
X0X00X0
ZZZZZZ1
0X11111
ZZZZ0ZZ
X0100X0
ZZZZ0ZZ
101X010
ZZZZZZZ
Æ
Z3 00X0XX0
Y1Z1ZZY
1X1XX11
11Z1ZZZ
1X1X1X0
X11X1X0
XX111X0 -
Z1ZZZZY
0X00101
ZZZZZZ1
0000101
1ZZZZZZ
10X00X0
Z1ZYZZY
0X11111
1ZZZZZZ
10100X0
YZZ1ZZZ
101X010 Æ
Z4 0X00101
YZY10YZ
1X1XX11
YZY1Z1Y
1X1X1X0
1ZY1Z1Y
X11X1X0
1ZYYZ1Y
XX111X0
ZZZZ01Y
0000XX0
ZZ1ZY1Y
00X00X0 -
ZZZZZZZ
Æ
YZ1ZY1Y
10X00X0
ZZYYZYZ
0X11111
YZYZY1Y
10100X0
YZY1YYY
101X010 Æ
Z5 000010X
Y1Y10YZ
1X1XX11
Y1Y1Z1Z
1X1X1X0
1YY1Z1Z
X11X1X0
11YYZ1Z
XX111X0
ZZZZ01Z
00000X0
0000X10
ZZ1ZY1Z
00X00X0
Z1ZZZZZ
0100101 -
YZ1ZY1Z
10X00X0
Z1YYZYZ
0X11111
YZYZY0Z
10100X0
YZY1YYY
101X010 Æ
Z6 X0X00X0
Z1Z11ZY
1X1XX11
Z1Z1YZZ
1X1X1X0
ZYZ1YZZ
X11X1X0
Z1ZYYZZ
XX111X0
ZZZZZZZ
Æ
ZZZZ1ZZ
0000110
ZZZZZZZ
Æ
ZYZZYZY
0100101 Æ -
Z1ZYYZY
0X11111
ZZZZZZZ
Æ
ZZZ1ZZZ
1011010 Æ
Z7 XX1111X
ZZZ00ZZ
1X10X11
1X1X011
ZZZ0Z0Z1X101X0
1X1X100
ZZZ0Z0ZX1101X0
X11X100
ZZYYZZZ
0000110
ZZYYZYZ
0100101 Æ
ZZ0YY0Z
10X00X0 - Æ
ZZZZYZZ
1011010 Æ
Z7
ZZZZZ0Z
XX111001
Z8 X010XX0
Z1ZZZZY
1X10X11
Z1Z1ZZY
1Z1Z011
Z1ZZZZZ
11 01X0
Z1Z1ZZZ
111X100
1X11100
ZYZZZZZ
X1101X0
Z1ZYZZZ
XX11100
ZZYZZZZ
0000110
ZYYZZZY
0100101 Æ
ZZ0ZZZZ
10000X0
Z1ZYZZY
0X11111 -
ZZZYZZZ
1011010 Æ
Z9 101XX1X
Z1ZZZZZ
1110X11
Z1ZZZZZ
111X011
ZYZZZ0Z
11101X0
ZYZZZYZ
111X100
Z1ZZZYZ
1X11100
0YZZZ0Z
X1101X0
0YZZZYZ
X11X100
01ZZZYZ
XX11100
YZYZZZZ
0000110
YYYZZYZ
0100101 Æ
ZZYZZ0Z
10000X0
Y1ZZZZZ
0X11111 Æ - Æ
Z10 1X1X11X
ZZZZ0ZZ
1110011
111X011
ZZZZZ0Z
1110100
ZZZZZYZ
111X100
ZZZZZYZ
1X11100
0ZZZZ0Z
01101X0
X110100
0ZZZZY1
X11X100
0ZZZZYZ
XX11100 0000110 0100101 Æ 10000X0 0X11111 Æ
ZZZZYZZ
1011010 - ¹ Æ ¹ Æ ¹ Æ ¹ Æ Æ ¹ Æ ¹ Æ Æ ¹ Æ Æ
Полученное минимальноепокрытие:
1X1XX11
XX1X1X0
00X0XX0
0X00101
X0X00X0
XX1111X
101XX1X
Cтоимость полученного покрытия равна36 ( стоимость исходного покрытия равна 53 ).
2. ПОСТРОЕНИЕФАКТОРИЗОВАННОГО ПОКРЫТИЯ
Покрытие, полученное наоснове простых импликант и выделения из них L-экстремалей, принято называть минимальным. Однако практикапоказывает, что дополнительная минимизация возможна при помощи факторизации.Таким образом, минимальным следует считать факторизованное покрытие, а не множествоL-экстремалей.
Факторизация покрытияоснована на операции m-произведения,которая предназначена для выделения общей части двух кубов. Эта операцияявляется поразрядной:
/> 0 при ai= bi=0, i = 1,n;
aim bi= 1 при ai= bi= 1, i = 1,n;
m во всехостальных случаях.
Символ m указывает координатуисходных кубов, которая различна в них, либо есть Х.
Куб, в котором хотя быодна координата является m,называется m-кубом иобозначается через еm. Такой куб может участвовать в m-произведении, тогда при умножении на координату m должна получаться координата m.
Стоимость для m-куба определяется путем подсчетачисла координат со значениями 0 и 1. Куб с наибольшей стоимостью считаетсямаксимальным. Если стоимость равна 0, то m-куб считается пустым, он равен Æ. Покрытие с учетом m-куба записывается в несколькоизмененном виде: под m-кубомфиксируются соответствующие ему кубы с сохранением тех координат, которыерасположены под символами m.
Алгоритм факторизациипокрытия является циклическим. Количество циклов равно числу уровней разложенияпокрытия ( числу m-кубов). В разложенном по многим уровням покрытии выделяются на i-м цикле m-куб еmi, Mi ( множество кубов с прочерками,соответствующее еmi),Ci (множество кубов, которые будутрассматриваться на ( i+1)-мцикле).
Алгоритм факторизацииможно сформулировать следующим образом:
1. Вычисляются m-произведения всех пар из Сi-1. В первом цикле С0= Е.Во втором цикле дело надо иметь с С1, в третьем – с С2 ит.д.
2. Выбирается m-куб с наибольшей стоимостью еmi. Если несколько кубов имеютодинаковую стоимость, то выбирается первый.
3. Покрытие оформляется разложенным надве части: нижнюю часть Мiи верхнюю часть Сi.Ci содержит оставшиеся от Сi-1 кубы после удаления из него кубов Мi и добавленный куб еmi. Видимо,
Ci =( Ci-1 – Mi ) È emi.
4. Если Сi состоит из одного куба или получаются пустые m-кубы, процесс факторизации следуетзакончить, в противном случае перейти к пункту 1.
Процесс факторизации по данному алгоритму удобноотражать в таблицах. Первый цикл представлен в табл. 9.Первый цикл факторизации Таблица 9
e1
1X1XX11
e2
XX1X1X0
e3
00X0XX0
e4
0X00101
e5
X0X00X0
e6
XX1111X
e1 1X1XX11 -
e2 XX1X1X0 mm1mmmm -
e3 00X0XX0 Æ mmmmmm0 -
e4 0X00101 mmmmmm1 mmmm1mm 0mm0mmm -
e5 X0X00X0 Æ mmmmmm1 m0m0mm0 mmm0mmm -
e6 XX1111X mm1mm1m mm1m1mm Æ mmmm1mm Æ -
e7 101XX1X 1m1mm1m mm1mmmm m0mmmmm Æ m0mmmmm mm1mm1m
Из этой таблицы видно,что еm1 = 1m1mm1m… Покрытие после первого цикла выглядитследующим образом:
/>
Так как С1 содержитбольше одного куба, осуществляется переход ко второму циклу ( табл. 10 ).
Второй цикл факторизации Таблица 10
е2
XX1X1X0
е3
00X0XX0
е4
0X00101
е5
X0X00X0
е6
XX1111X
е2 XX1X1X0 -
е3 00X0XX0 mmmmmm0 -
е4 0X00101 mmmm1mm 0mm0mmm -
е5 X0X00X0 mmmmmm0 m0m0mm0 mmm0mmm -
е6 XX1111X mm1m1mm Æ mmmm1mm Æ -
еm1 1m1mm1m mm1mmmm Æ Æ Æ mm1mm1m
Очевидно, что еm2 = m0m0mm0.
Покрытие после второгоцикла факторизации выглядит следующим образом:
/>
Так как С2содержит больше одного куба, осуществляется переход к третьему циклу ( табл. 11).Третий цикл факторизации Таблица 11
e2
XX1X1X0
e4
0X00101
e6
XX1111X
e2 XX1X1X0 -
e4 0X00101 mmmm1mm -
e6 XX1111X mm1m1mm mmmm1mm -
em2 m0m0mm0 mmmmmm0 mmm0mmm Æ
Из таблицы 11 видно, чтоеm3 = mm1m1mm.
Покрытие после третьегоцикла выглядит так:
/>
Так как С3содержит больше одного куба переходим к четвертому циклу (табл. 12).
Таблица12
Четвертый циклфакторизации
e4
0X00101
е4 0X00101 -
еm3 mm1m1mm mmmm1mm
Ясно, что еm4 = mmmm1mm.
Факторизованное покрытиевыглядит следующим образом:
/>
Чтобы определить стоимость факторизованногопокрытия, нужен соответствующий алгоритм. Его сущность можно изложить следующимобразом:
1. определить стоимость рассматриваемогокуба покрытия;
2. если куб является маскирующим (m-куб), то добавить к стоимости 2;
3. если куб является обычным, то при Si > 1 добавить к стоимости 1, впротивном случае ( Si = 1) добавлять 1 не нужно;
4. полученные стоимости кубов сдобавлениями сложить.
В полученном выше факторизованном покрытии 11 кубов,его стоимость составляет 30. До факторизации стоимость покрытия составляла 36.
3. СОСТАВЛЕНИЕ ЛОГИЧЕСКОЙ СХЕМЫ НА ОСНОВЕ ДАННОГО БАЗИСАЛОГИЧЕСКИХ ЭЛЕМЕНТОВ
По любому кубическомупокрытию можно построить логическую схему. По факторизованному покрытию схемастроится следующим образом. Обычные кубы отражаются на схеме как элементы &с числом входов, равным стоимости куба. Прочеркнутые координаты на вход этихэлементов не подаются. Они учитываются в маскирующих кубах в качестве общихсомножителей. Выходные сигналы обычных кубов, расположенных под рассматриваемымm-кубом, суммируются, затем логическаясумма этих кубов подается на вход маскирующего куба, который отображается насхеме как элемент &. Логическая схема в булевом базисе, построенная пофакторизованному покрытию, показана на рис.1.
Стоимость кубов М1и М2, а также куба ХХ-Х1Х-, входящего в М3, равна 1.Поэтому соответствующие им переменные подаются непосредственно на входыэлементов ИЛИ (12, 11 и 10 соответственно). Умножение на координаты куба еm1 производится в элементе 15, на координаты куба еm2 – в элементе 14, на координаты куба еm3 – в элементе 13. Кубы еm3 и еm4 имеют общую пятую координату. Поэтому выходной сигналэлемента 13, соответствующего еm3, логически суммируется с выходным сигналом элемента 8, азатем логическая сумма поступает на вход элемента 16, где происходит умножениена координаты куба еm4.
Стоимость даннойлогической схемы равна 30, такова стоимость и факторизованного покрытия. Такимобразом, можно сделать предварительное заключение о соответствии составленнойсхемы факторизованному покрытию.
/>
Рис.1
Дальше необходимо составить схему в универсальномбазисе элементов, который в настоящее время широко применяется. Универсальныйбазис элементов – это система элементов, реализующая функцию И-НЕ или ИЛИ-НЕ.
Логическую схему наоснове заданного универсального базиса легче всего построить по логическойсхеме на элементах булевого базиса элементов. Для этого нужно воспользоватьсясоответствием между элементами булевого базиса и заданного универсальногобазиса ( табл. 13 ). В данном случае используетсябазис ИЛИ-НЕ.
Таблица 13 Булевой Базис Универсальный базис ИЛИ-НЕ
/>
/>
/>
/>
Заменяя элементы, неследует стремиться к полной замене. Если производить замену формально ( один кодному ), то в связи между элементами окажется два последовательно включенныхинвертора, что равносильно их отсутствию.
Логическая схема наоснове элементов базиса ИЛИ-НЕ показана на рис.2.
функция покрытие логический кубический
/>
Рис. 2
4. НАХОЖДЕНИЕ ПО ПИ-АЛГОРИТМУ РОТА ЕДИНИЧНОГО ПОКРЫТИЯ
Построенную логическую схемунужно проверить, для этого находится покрытие схемы. В табл. 15 отраженопокрытие схемы, представленной на рис. 2. При нахождении покрытия схемыиспользуются покрытия отдельных элементов схемы ( табл. 14 ).
Таблица 14Элемент Таблица истинности Покрытие ИЛИ
1 2 3
0 0 0
0 1 1
1 0 1
1 1 1
1 2 3
0 0 0
Х 1 1
1 Х 1 И
0 0 0
0 1 0
1 0 0
1 1 1
Х 0 0
0 Х 0
1 1 1 ИЛИ-НЕ
0 0 1
0 1 0
1 0 0
1 1 0
0 0 1
Х 1 0
1 Х 0
Обозначения: 1,2 – входы, 3 –выход элементов.
Таблица 151 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Примечания Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х 1 С(f) 0 1
П191 Ú 18 0 1
Пересечение с (Сf) (*)
Х Х 1 0 1
Х 1 Х 0 1
1 Х Х 0 1
П180 Ú 14, 15, 17
Х Х 1 0 1
Х 1 Х 0 1
1 Х Х 0 1 Пересечение с (*) (**) 1 Х Х 0 1 0 1
П171 Ú 5, 16
1
1
1
Х Х 0 1 0 1
Х 1 0 1 0 1
1 Х 0 1 0 1 Пересечение с (**) (***)
Х 1 Х Х 0 1 0 1
1 Х Х Х 0 1 0 1
П160 Ú 8, 13
1
1
1
1
1
1
Х 1 Х Х 0 1 0 1
1 Х Х Х 0 1 0 1
Х 1 Х 1 0 1 0 1
1 Х Х 1 0 1 0 1
Х 1 1 Х 0 1 0 1
1 Х 1 Х 0 1 0 1 Пересечение с (***) (****) 0 0 0 0 1 1 Х Х Х 0 1 0 1
П81 Ú 1, 3, 4, 6, 7
0 Х 0 0 1 0 1 0 Х 0 0 1 0 1
0 Х 0 0 1 0 1
0 Х 0 0 1 0 1
0 Х 0 0 1 0 1
0 Х 0 0 1 0 1
1 1 Х Х 0 1 0 1
1 Х Х Х 0 1 0 1
1 1 Х 1 0 1 0 1
1 Х Х 1 0 1 0 1
1 1 1 Х 0 1 0 1
1 Х 1 Х 0 1 0 1 Пересечение с (****) (*****) 1 Х 0 1 Х Х 0 1 0 1
П131 Ú 3, 10
1 1
1 1
1 1
1 1
1 1
1 1
Х 0 1 Х Х 0 1 0 1
1 0 1 Х Х 0 1 0 1
Х 0 1 Х 1 0 1 0 1
1 0 1 Х 1 0 1 0 1
Х 0 1 1 Х 0 1 0 1
1 0 1 1 Х 0 1 0 1 Пересечение с (****) (*****’)
Х Х Х Х Х Х Х
Х Х Х Х Х Х 0
Х 1 0 1 Х Х 0 1 0 1
Х Х 0 1 Х Х 0 1 0 1
П100 Ú 7, 9
Х Х 1 Х 1 Х Х
Х Х 1 Х 1 Х 0
Х Х 1 Х 1 Х Х
Х Х 1 Х 1 Х 0
Х Х 1 Х 1 Х Х
Х Х 1 Х 1 Х 0
Х Х 1 Х 1 Х Х
Х 1 0 1 Х Х 0 1 0 1
Х Х 0 1 Х Х 0 1 0 1
1 1 0 1 Х Х 0 1 0 1
1 Х 0 1 Х Х 0 1 0 1
Х 1 0 1 Х 1 0 1 0 1
Х Х 0 1 Х 1 0 1 0 1
1 1 0 1 Х 1 0 1 0 1 Пересечение с (*****’) (******) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Примечания
Х Х 1 Х 1 Х 0
Х Х 1 Х 1 Х Х Х Х 1 Х 1 Х 0
Х Х 1 Х 1 Х Х
Х Х 1 Х 1 Х 0
1 Х 0 1 Х 1 0 1 0 1
Х 1 0 1 1 Х 0 1 0 1 Х Х 0 1 1 Х 0 1 0 1
1 1 0 1 1 Х 0 1 0 1
1 Х 0 1 1 Х 0 1 0 1 Пересечение с (*****’) (******) Х Х Х 1 Х 1 Х Х 1 0 1 Х Х 0 1 0 1
П91 Ú 4, 6
Х Х 1 1 1 1 Х
Х Х 1 1 1 1 0
Х Х 1 1 1 1 Х
Х Х 1 1 1 1 0
Х Х 1 1 1 1 Х
Х Х 1 1 1 1 0
Х Х 1 1 1 1 Х
Х Х 1 1 1 1 0
Х Х 1 1 1 1 Х
Х Х 1 1 1 1 0
Х Х 1 1 1 1 Х
Х Х 1 1 1 1 0
Х 1 0 1 Х Х 0 1 0 1
Х 1 0 1 Х Х 0 1 0 1
1 1 0 1 Х Х 0 1 0 1
1 1 0 1 Х Х 0 1 0 1
Х 1 0 1 Х 1 0 1 0 1
Х 1 0 1 Х 1 0 1 0 1
1 1 0 1 Х 1 0 1 0 1
1 1 0 1 Х 1 0 1 0 1
Х 1 0 1 1 Х 0 1 0 1
Х 1 0 1 1 Х 0 1 0 1
1 1 0 1 1 Х 0 1 0 1
1 1 0 1 1 Х 0 1 0 1 Пересечение с (******) (*******) 0 0 0 0 1 Х 0 Х 0 1
П141 Ú 2, 4, 7, 11
0 0 0
0 0 0
0 0 0
0 1 Х 0 Х 0 1
0 1 Х 0 1 0 1
0 1 1 0 Х 0 1 Пересечение с (**) (***’)
Х Х Х Х 0 Х Х
0 Х Х Х Х Х Х
0 1 Х 0 Х 0 1
0 1 Х 0 Х 0 1
П110 Ú 1, 5
Х 0 Х 0 0 Х 0
0 0 Х 0 Х Х 0
Х 0 Х 0 0 Х 0
0 0 Х 0 Х Х 0
Х 0 Х 0 0 Х 0
0 0 Х 0 Х Х 0
0 1 Х 0 Х 0 1
0 1 Х 0 1 0 1
0 1 1 0 Х 0 1
0 1 Х 0 Х 0 1
0 1 Х 0 1 0 1
0 1 1 0 Х 0 1 Пересечение с (***') (****’) 1 1 1 0 Х 1 0 Х 0 1
П151 Ú 1, 3, 6, 12
1 1 1
1 1 1
1 1 1
0 Х 1 0 Х 0 1
0 Х 1 0 1 0 1
0 1 1 0 Х 0 1 Пересечение с (**) (***’’)
Х Х Х Х Х Х 1
Х 0 Х Х Х Х Х
0 Х 1 0 Х 0 1
0 Х 1 0 Х 0 1
П120 Ú 2, 7
1 Х 1 Х Х 1 1
1 0 1 Х Х 1 Х
1 Х 1 Х Х 1 1
1 0 1 Х Х 1 Х
1 Х 1 Х Х 1 1
1 0 1 Х Х 1 Х
0 Х 1 0 Х 0 1
0 Х 1 0 1 0 1
0 1 1 0 Х 0 1
0 Х 1 0 Х 0 1
0 Х 1 0 1 0 1
0 1 1 0 Х 0 1 Пересечение с (***’') (****’’)
Как следует из табл. 15, ищетсяпокрытие схемы, обеспечивающее единичное значение выходной функции. Этоозначает, что на выходе элемента 19 должна быть единица (соответственно, навыходе элемента 18 должен быть 0). По табл. 15 можно увидеть что значение 0 навыходе элемента 18 будет, если на выходе хотя бы одного из элементов 14, 15,или 17 будет 1. Далее осуществляется пересечение покрытия элемента 18 спокрытием элемента 19. Затем последовательно фиксируются покрытия и пересеченияприменительно к элементам 17, 14 и 15. Результаты пересечения покрытийотмечаются «звездочками».
Покрытие схемы осуществляется поветвям. После покрытия элементов первого яруса находятся кубы множества L-экстремалей Z. В табл. 15 эти кубывыделены подчеркиванием.
Для большей наглядности выпишемэти кубы:
0X00101
XX1X1X0
XX1111X
X0X00X0
00X0XX0
1X1XX11
101XX1X
Это найденное покрытиеточно совпадает с ранее полученным покрытием Е. Следовательно, факторизацияминимального покрытия и построение логической схемы осуществлены верно.
Далее необходимопроизвести изменение схемы с учетом конкретных характеристик элементов данногоуниверсального базиса, а именно Квх (коэффициент входа) и Кр(коэффициент разветвления). Современные элементы имеют сравнительно большиезначения Квх и Кр, но в данном случае они выбраны малыми:Квх = 4; Кр = 2.
Применительно к схеме нарис. 2 можно сказать что нарушений по Квх нет, но нарушенотребование по Кр в двух случаях. Измененная схема представлена нарис. 3. На ней помимо элементов 15, 16, 17 и 18, исправляющих нарушения по Кр,имеются инверторы для каждой координаты куба.
Вместо 19 элементов нарис. 2 стало 32 элемента на рис. 3.
5. СИНТЕЗКОНТРОЛИРУЮЩЕГО ТЕСТА. КОНТРОЛЬ СХЕМЫ ТЕСТОМ
Синтезировать контрольный тест для логической схемы– найти множество кубов, которые позволяют выявлять неисправности схемы. Если всхеме нет неисправностей, то на каждом кубе получается так называемая эталоннаяреакция схемы. Множество кубов порождает множество эталонных реакций схемы.
При наличии неисправностив схеме реакция хотя бы на одном кубе должна измениться. В итоге множество реальныхреакций не совпадает с множеством эталонных реакций. Это будет говорить о том,что неисправность выявляется. Если тест позволяет выявлять любую неисправность,то он обладает 100-процентной полнотой. Однако, это не всегда бывает так.Обычно тест не обеспечивает выявление всех неисправностей, его полнота менее100%.
В данной курсовой работерассматривается ограниченный класс неисправностей:
1). Выход элементатождественно равен 0,
2). Выход элементатождественно равен 1.
Считается, что в данныймомент времени в схеме может быть только одна неисправность. Это означает, чтосхема является высоконадежной.
Синтез тестаосуществляется по методу активизации пути. Сущность этого метода заключается втом, что, задав какую-либо неисправность на выбранном входе схемы, нужнообеспечить условия для беспрепятственного прохождения сигнала, связанного сзаданной неисправностью, на выход схемы. Это означает, что при прохожденииуказанного сигнала через элемент ИЛИ-НЕ на всех других его входах надообеспечить нули. В свою очередь обеспечение таких входных сигналов связано свыбором подходящей строки покрытия элемента, с которого снимается нужныйсигнал.
/>
Рис. 3
Процесс активизации путейсхемы (рис.3) отображен в табл. 16. Всего оказалось 20 путей.Контролирующий тест Таблица 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Пути 1 0 0 0 1 1 0 0’1 1 1 0 0 1 1 0 1 0 0 0 1’ 0 1 0 0’ 0 0 0 1 0 1’ 0’ 1, 8,21, 25, 31,32 1 0 1 1 0 1 0 0’1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1’ 0 1 0 0 0’ 1’ 1, 8, 26, 31,32 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0’ 0 1’ 0 1’ 1 0’ 0 0’ 0 1’ 0’ 1’ 0’ 1, 19, 23, 27, 29, 30, 31, 32 1 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 0’ 0 0 1 0 0 1’ 0’ 2, 25, 31, 32 1 1 1 0 0 1 0 0 0’ 0 1 1 0 1 1 0 1 0 0 0 0 1’ 1 0 0 0’ 0 1 0 0 1’ 0’ 2, 9, 22,26, 31,32 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0’ 0 0 0 1’ 1 0 0 0’ 0 1’ 0’ 1’ 0’ 3, 19, 23, 27, 29, 30, 31, 32 0 1 1 0 1 1 0 1 0 0’ 1 0 0 1 1 0 1 0 0’ 0 0’ 1 1’ 0 0’ 0 0’ 1 0’ 1’ 0’ 1’ 3, 10, 28, 29, 30, 31, 32 1 0 1 1 0 1 0 0 1 0’ 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1’ 0 1 0 0 0’ 1’ 3, 10, 26, 31, 32 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0’ 1’ 0 1 0’ 0 0 0 1’ 1 0 0 0 0 1’ 0’ 1’ 0’ 4, 15, 16, 19, 23, 29, 30, 31,32 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0’ 1’ 1 0 0 1 0 0 1 0 0’ 0 0 0 1 0 1’ 0’ 4, 15,16,25,31,32 0 0 1 1 1 1 0 1 1 0 0’ 0 0 1 0 1 1 0 0 1’ 0 0 1 0’ 0 0 0 1’ 0’ 1’ 0’ 1’ 4, 11, 20, 24, 28, 29, 30, 31, 32 1 0 0 0 1 1 0 0 1 1 1 0’ 0 1 1 0 1 0 0 0 1’ 0 1 0 0’ 0 0 0 1 0 1’ 0’ 5,12,21,25, 31,32 0 0 1 1 1 1 0 1 1 0 0 0’ 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1’ 0’ 1’ 5, 12, 30, 31, 32 0 1 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 0’ 0 0 0 1’ 1 0 0 0’ 0 1’ 0’ 1’ 0’ 6,19,23,27,29,30,31,32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Пути 0 0 1 1 0 1 1 1 1 0 0 1 0’ 0 0 1 0 1 0 1’ 0 0 1 0’ 0 0 0 1’ 0’ 1’ 0’ 1’ 6, 13, 20, 24, 28, 29, 30, 31, 32 1 0 1 1 0 1 0 0 1 0 0 1 0’ 1 0 1 1 0 0 1 0 0 1 0 0 1’ 0 1 0 0 0’ 1’ 6, 13, 26, 31, 32 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0’ 0’ 0 0 0 0’ 1 1 0 1’ 0 0 1 0 0’ 1’ 7, 17, 18, 22, 26, 31, 32 0 0 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0’ 1’ 0 0 0 0 1 1 0’ 0 0 0 1 0 1’ 0’ 7,17,18,25,31,32 0 0 1 0 1 0 1 1 1 0 1 0 1 0’ 1 0 0 1 0 0 0 0 1 1’ 0 0 0 0’ 1’ 0’ 1’ 0’ 7, 14, 24, 28, 29, 30, 31, 32 0 1 0 0 1 0 1 1 0 1 1 0 1 0’ 1 0 1 0 1 0 0 0 0 1 0 0 1’ 0 0’ 1’ 0’ 1’ 7, 14, 27, 29, 30, 31, 32
После заполнения всехстрок таблицы из нее следует выписать наборы входных переменных ссоответствующими реакциями. При этом один набор с переменной 1’ распадается надва набора, в одном из них 1’ дает 1, а в другом – 0. В общей системе наборовобычно получаются одинаковые наборы. Лишние нужно удалить. Оставшиеся ( табл.17 ) наборы с эталонными реакциями и являются тестом. Таблица 17 Реакция Наборы Реакция Наборы 0 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0
Всегополучилось 24 набора.
Чтобы проверить схему,надо задать три неисправности: одна касается какого-либо элемента ближе ковходам схемы, другая – к середине схемы, третья – к выходу схемы.
Надлежит установить,обнаруживается или нет каждая заданная неисправность тестом. При этом нужнобрать те тестовые наборы, которые как раз и предназначены для обнаружениязаданной неисправности.
Проверка схемы проведенав табл. 18. В соответствующем столбце фиксируется ошибка, сведения длястолбцов, расположенных левее, берутся из табл.16, остальные заполняютсясамостоятельно с учетом введенной ошибки. Полученная реакция сравнивается сэталонной. Таким образом устанавливается, обнаруживается или нет заданнаянеисправность. Проверка логической схемыконтролирующим тестом Таблица 18№ набора 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Эталонная реакция Пути 7 0 1 1 0 1 1 0
1 0 1 1 0 0 1
Выход 10 = 1
1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 3, 10, 28, 29, 30, 31, 32 9 0 1 0 1 1 0 1 1 0 1 0 0 1 0
Выход 19 = 1
0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 4, 15, 16, 19, 23, 27, 29, 30, 31,32 11 0 0 1 1 1 1 0 1 1 0 0 0 0 1
Выход 28 = 0
0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 4, 11, 20, 24, 28, 29, 30, 31, 32
ЗАКЛЮЧЕНИЕ
В данной работе явыполнил синтез логической схемы по заданному в кубической форме покрытию. Приэтом мною предварительно была проведена минимизация и факторизация покрытия.Первоначальная стоимость покрытия была равна 48, после нахождения множествапростых импликант она увеличилась на 5 (что составило 10,4% от первоначальнойстоимости), после нахождения множества L-экстремалей стоимость уменьшилась на 17 (32%), а послепроведения факторизации покрытия еще на 6 (16,7%). Итоговая стоимость покрытияполучилась равной 30. Синтез схемы осуществлялся мною последовательно: сначалабыла построена схема в булевом базисе, затем по этой схеме была построена схемав универсальном базисе ИЛИ-НЕ (при этом использовались соответствия междуэлементами булевого и универсального базисов). После составления схемы вуниверсальном базисе была проведена проверка схемы путем нахождения единичногопокрытия. Так как в ходе проверки были найдены все кубы множества L-экстремалей, то схема была признанаправильной. И наконец, была составлена схема с учетом реально имеющихсяограничений, а именно: Квх и Кр. Обычно эта схемаполучается довольно громоздкой (до 50 и более элементов), но в моем случае Квхбыл равен 4, из-за чего схема увеличилась лишь незначительно: если в схеме вуниверсальном базисе было 19 элементов, то в конечной схеме их было только 32.Напоследок мною был синтезирован контролирующий тест и проведена проверка схемытестом, которая показала, что заданная неисправность успешно обнаруживаетсятестом.
ЛИТЕРАТУРА
1. ТрихановА.В. Синтез логических схем. Учебное пособие.-Томск,2007.
2. Майоров С.А. идр. Проектирование ЦВМ. – М.: ВШ,2006.
3. Миллер Р. Теорияпереключательных схем. Том 1. – М.: Наука,2006.
4. Триханов А.В. Алгоритмизацияи микропрограммирование операций ЭВМ (множества, графы, кубы, кубическиепокрытия). Учебное пособие. – Томск: Изд-во ТПУ,2005.