Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


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

Тип Реферат
Предмет Математика
Просмотров
1394
Размер файла
128 б
Поделиться

Ознакомительный фрагмент работы:

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

Министерство образования Российской Федерации

Томский политехнический университет

Факультет автоматики и вычислительной техники

Кафедра вычислительной

техники

Курсовая работа

по дисциплине “Теория автоматов”

на тему: «Синтез и анализ логической схемы при кубическом задании булевой функции»

Томск 2009


СОДЕРЖАНИЕ

Введение

1. Нахождение минимального покрытия

2. Построение факторизованного покрытия

3. Составление логической схемы на основе данного базиса логических элементов

4. Нахождение по пи-алгоритму Рота единичного покрытия

5. Синтез контролирующего теста. Контроль схемы тестом

Заключение

Литература


ВВЕДЕНИЕ

Аппарат алгебры логики широко применяется в теории ЦВМ, в частности для решения задач анализа и синтеза схем. При решении задачи синтеза исходное логическое выражение, описывающее некоторую логическую функцию, преобразуется и упрощается так, чтобы каждый член полученного эквивалентного логического выражения мог быть представлен простой схемой. Таким образом, при синтезе вычислительных и управляющих схем составляется математическое описание задачи в виде формул алгебры логики. Затем производится минимизация исходной формулы и из числа эквивалентных логических схем выбирается та, которая допускает наиболее простую реализацию.

В данной курсовой работе стоит задача синтеза схемы, реализующей функцию, заданную кубическим комплексом к(f). В табл. 1 приведено исходное покрытие из 8 кубов. Логическую схему следует построить в универсальном базисе элементов ИЛИ-НЕ, который характеризуется коэффициентом объединения по входу к(вх)=4 и коэффициентом разветвления по выходу к(р)=2. Стоимость покрытия равна 48.

Таблица 1

Обозначение кубаПокрытиеРазмерность куба
a1011X106
b1X1XX114
c1011X116
dXX1X1X03
e0X111116
f00X0XX04
g0X001016
h10X00X05

Порядок выполнения работы можно определить следующим образом:

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
01X

bi

00Y0
1Y11
X01X

Если значение Y получается только в одной координате, то произведение кубов a и b дает так называемый вновь образованный куб, в котором величина Y заменяется на X. Если же имеется более одной координаты Y, то звездчатое произведение дает 0.

Процесс нахождения множества простых импликант является циклическим. В каждом цикле вначале удаляются те кубы исходного покрытия, которые являются гранями других кубов этого покрытия. Далее удаляются кубы исходного покрытия, являющиеся гранями кубов покрытия. Должны быть удалены полученные при *-произведении кубы, являющиеся гранями кубов покрытия. И наконец, удаляются полученные кубы с размерностью, на единицу меньшей номера цикла. Оставшиеся в таблице кубы передаются на следующий цикл *-произведения. Циклы выполняются до тех пор, пока перестанут появляться вновь образованные кубы. Процесс нахождения множества простых импликант для 35-го варианта приведен в табл. 3,4,5,6. Куб «с» не используется при нахождении данного множества, т.к. он входит в куб «b».

1 цикл нахождения множества простых импликант Таблица 3

1011X101X1XX11XX1X1X00X1111100X0XX00X00101
1011X10-
1X1XX111011X1X-
XX1X1X010111101X1X11X-
0X11111ÆXX111110X1111X-
00X0XX0ÆÆ00101X0Æ-
0X00101ÆÆÆÆ000010X-
10X00X0101X010101001X1010XX0ÆX0X00X0Æ

2 цикл нахождения множества простых импликант Таблица 4

1Х1ХX11XX1X1X000X0XX00X001011011X1X101X0101X1X11XXX11111101001X0X1111X1010XX0000010X
1X1XX11-
XX1X1X0-
00X0XX0-
0X00101-
1011X1X1011X11101111XÆÆ-
101X010101X01X101XX10Y010010Æ1011010-
1X1X11X1X1X1111X1X110Y010110Æ101111X101XY10-
XX111111X11111XX1111XÆÆ1011111Æ1X11111-
101001X10100111010Y10Y010010Æ101X01X10100101010Y1XÆ-
0X1111XXX111110X11110001Y110ÆX01111XÆYX1111X0X11111Æ-
1010XX01010X1X10101X0X010XX0Æ101XX1010100101010110Æ1010010Æ-
000010XÆ00Y010000001000000101ÆÆÆÆÆÆÆ-
X0X00X0101001XX010XX000X00X00000Y01101Y01010100101010Y10Æ1010010Æ10100X00000Y00

3 цикл нахождения множества простых импликант Таблица 5

1X1XX11XX1X1X000X0XX00X001011011X1X1X1X11X000010XX0X00X0101X01X1010X1X101XX10XX1111X
1X1XX11-
XX1X1X0-
00X0XX0-
0X00101-
1011X1X-
1X1X11X-
000010X-
X0X00X0-
101X01X101X011101XX10X010010Æ101101X101XX1XÆ1010010-
1010X1X1010X111010110X010X10Æ101XX1X101011XÆ1010010101001X-
101XX10101XX1X101X110X010X10Æ1011X10101X110Æ1010010101X0101010X10-
XX1111X1011111XX11110001X110Æ101111X1X1111XÆÆ1011X1X101X11X1011110-
X010XX01010X1XX0101X00010XX0Æ101XX10101011000X0100X0100X010100101010X101010X10X01X110

4 цикл нахождения множества простых импликант Таблица 6

1X1XX11XX1X1X000X0XX00X00101000010XX0X00X0XX1111XX010XX0101XX1X
1X1XX11-
XX1X1X0-
00X0XX0-
0X00101-
000010X-
X0X00X0-
XX1111X-
X010XX0-
101XX1X101XX11101X110X010X10ÆÆ1010010101111X1010X10-
1X1X11X1X1X1111X1X110X010110ÆÆ1010X101X1111X1010110101X11X

В таблицах 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 # biai
01X

bi

0ZY1
1YZ0
XZZZ

Операция вычитания из куба а куба 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

123456789101112
Z11X1XX11-

0ZZZZ0Y

XX1X1X0

YZ0ZZ0Y

00X0XX0

YZYZZYZ

0X00101

YZYZZY0

000010X

0Z0ZZ0Y

X0X00X0

0ZZZZZZ

0X1111X

0ZZZZ0Y

X010XX0

ZZZZZZ0

101XX10

ZZZZZZ0

1X1X110

Z2XX1X1X0

ZZZZ0ZY

1X1XX11

-

ZZ0Z0ZZ

0000XX0

00X00X0

ZZYZZZY

0X00101

ZZYZZZ1

000010X

ZZ0ZYZZ

X0X00X0

ZZZZZZ1

0X11111

ZZZZ0ZZ

X0100X0

ZZZZ0ZZ

101X010

ZZZZZZZ

Æ

Z300X0XX0

Y1Z1ZZY

1X1XX11

11Z1ZZZ

1X1X1X0

X11X1X0

XX111X0

-

Z1ZZZZY

0X00101

ZZZZZZ1

0000101

1ZZZZZZ

10X00X0

Z1ZYZZY

0X11111

1ZZZZZZ

10100X0

YZZ1ZZZ

101X010

Æ
Z40X00101

YZY10YZ

1X1XX11

YZY1Z1Y

1X1X1X0

1ZY1Z1Y

X11X1X0

1ZYYZ1Y

XX111X0

ZZZZ01Y

0000XX0

ZZ1ZY1Y

00X00X0

-

ZZZZZZZ

Æ

YZ1ZY1Y

10X00X0

ZZYYZYZ

0X11111

YZYZY1Y

10100X0

YZY1YYY

101X010

Æ
Z5000010X

Y1Y10YZ

1X1XX11

Y1Y1Z1Z

1X1X1X0

1YY1Z1Z

X11X1X0

11YYZ1Z

XX111X0

ZZZZ01Z

00000X0

0000X10

ZZ1ZY1Z

00X00X0

Z1ZZZZZ

0100101

-

YZ1ZY1Z

10X00X0

Z1YYZYZ

0X11111

YZYZY0Z

10100X0

YZY1YYY

101X010

Æ
Z6X0X00X0

Z1Z11ZY

1X1XX11

Z1Z1YZZ

1X1X1X0

ZYZ1YZZ

X11X1X0

Z1ZYYZZ

XX111X0

ZZZZZZZ

Æ

ZZZZ1ZZ

0000110

ZZZZZZZ

Æ

ZYZZYZY

0100101

Æ-

Z1ZYYZY

0X11111

ZZZZZZZ

Æ

ZZZ1ZZZ

1011010

Æ
Z7XX1111X

ZZZ00ZZ

1X10X11

1X1X011

ZZZ0Z0Z1X101X0

1X1X100

ZZZ0Z0ZX1101X0

X11X100

ZZYYZZZ

0000110

ZZYYZYZ

0100101

Æ

ZZ0YY0Z

10X00X0

-Æ

ZZZZYZZ

1011010

Æ
Z7

ZZZZZ0Z

XX111001

Z8X010XX0

Z1ZZZZY

1X10X11

Z1Z1ZZY

1Z1Z011

Z1ZZZZZ

11 01X0

Z1Z1ZZZ

111X100

1X11100

ZYZZZZZ

X1101X0

Z1ZYZZZ

XX11100

ZZYZZZZ

0000110

ZYYZZZY

0100101

Æ

ZZ0ZZZZ

10000X0

Z1ZYZZY

0X11111

-

ZZZYZZZ

1011010

Æ
Z9101XX1X

Z1ZZZZZ

1110X11

Z1ZZZZZ

111X011

ZYZZZ0Z

11101X0

ZYZZZYZ

111X100

Z1ZZZYZ

1X11100

0YZZZ0Z

X1101X0

0YZZZYZ

X11X100

01ZZZYZ

XX11100

YZYZZZZ

0000110

YYYZZYZ

0100101

Æ

ZZYZZ0Z

10000X0

Y1ZZZZZ

0X11111

Æ-Æ
Z101X1X11X

ZZZZ0ZZ

1110011

111X011

ZZZZZ0Z

1110100

ZZZZZYZ

111X100

ZZZZZYZ

1X11100

0ZZZZ0Z

01101X0

X110100

0ZZZZY1

X11X100

0ZZZZYZ

XX11100

00001100100101Æ10000X00X11111Æ

ZZZZYZZ

1011010

-
¹Æ¹Æ¹Æ¹ÆƹƹÆƹÆÆ

Полученное минимальное покрытие:

1X1XX11

XX1X1X0

00X0XX0

0X00101

X0X00X0

XX1111X

101XX1X

Cтоимость полученного покрытия равна 36 ( стоимость исходного покрытия равна 53 ).

2. ПОСТРОЕНИЕ ФАКТОРИЗОВАННОГО ПОКРЫТИЯ

Покрытие, полученное на основе простых импликант и выделения из них L-экстремалей, принято называть минимальным. Однако практика показывает, что дополнительная минимизация возможна при помощи факторизации. Таким образом, минимальным следует считать факторизованное покрытие, а не множество L-экстремалей.

Факторизация покрытия основана на операции m-произведения, которая предназначена для выделения общей части двух кубов. Эта операция является поразрядной:

0 при ai= bi= 0, i = 1,n;

aimbi= 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

e11X1XX11-
e2XX1X1X0mm1mmmm-
e300X0XX0Æmmmmmm0-
e40X00101mmmmmm1mmmm1mm0mm0mmm-
e5X0X00X0Æmmmmmm1m0m0mm0mmm0mmm-
e6XX1111Xmm1mm1mmm1m1mmÆmmmm1mmÆ-
e7101XX1X1m1mm1mmm1mmmmm0mmmmmÆm0mmmmmmm1mm1m

Из этой таблицы видно, что еm1 = 1m1mm1m.. Покрытие после первого цикла выглядит следующим образом:

Так как С1 содержит больше одного куба, осуществляется переход ко второму циклу ( табл. 10 ).


Второй цикл факторизации Таблица 10

е2

XX1X1X0

е3

00X0XX0

е4

0X00101

е5

X0X00X0

е6

XX1111X

е2XX1X1X0-
е300X0XX0mmmmmm0-
е40X00101mmmm1mm0mm0mmm-
е5X0X00X0mmmmmm0m0m0mm0mmm0mmm-
е6XX1111Xmm1m1mmÆmmmm1mmÆ-
еm11m1mm1mmm1mmmmÆÆÆmm1mm1m

Очевидно, что еm2 = m0m0mm0.

Покрытие после второго цикла факторизации выглядит следующим образом:

Так как С2 содержит больше одного куба, осуществляется переход к третьему циклу ( табл. 11 ).

Третий цикл факторизации Таблица 11

e2

XX1X1X0

e4

0X00101

e6

XX1111X

e2XX1X1X0-
e40X00101mmmm1mm-
e6XX1111Xmm1m1mmmmmm1mm-
em2m0m0mm0mmmmmm0mmm0mmmÆ

Из таблицы 11 видно, что еm3 = mm1m1mm.

Покрытие после третьего цикла выглядит так:

Так как С3 содержит больше одного куба переходим к четвертому циклу (табл. 12).

Таблица 12

Четвертый цикл факторизации

e4

0X00101

е40X00101-
еm3mm1m1mmmmmm1mm

Ясно, что е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 – выход элементов.

Таблица 15

1 2 3 4 5 6 78 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 11 Х Х Х 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 78 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 00 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 путей.

Контролирующий тест Таблица 16
1 2 3 4 5 6 78 9 10 11 12 13 1415 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32Пути
1 0 0 0 1 1 00’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 00’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 10 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 00 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 00 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 11 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 01 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 00 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 11 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 00 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 01 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 00 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 01 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 11 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 78 9 10 11 12 13 1415 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32Пути
0 0 1 1 0 1 11 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 00 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 10 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 11 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 11 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 11 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
РеакцияНаборыРеакцияНаборы
00 0 1 1 0 1 100 0 1 0 1 1 1
11 0 1 1 0 1 000 0 1 0 1 0 1
01 1 0 0 1 0 110 1 0 0 1 0 1
01 1 1 0 0 1 010 0 0 0 1 1 0
00 1 1 0 1 0 100 0 1 1 0 1 0
10 1 1 0 1 1 011 0 1 0 0 1 0
00 1 0 1 1 0 111 0 0 0 0 1 0
01 0 0 1 0 1 000 0 1 1 0 0 1
10 0 1 1 1 1 001 0 1 1 0 0 0
00 1 0 0 1 1 110 0 1 0 1 1 0
10 0 1 1 0 1 110 0 1 0 1 0 0
11 1 1 0 0 1 100 1 0 0 1 0 0

Всего получилось 24 набора.

Чтобы проверить схему, надо задать три неисправности: одна касается какого-либо элемента ближе ко входам схемы, другая – к середине схемы, третья – к выходу схемы.

Надлежит установить, обнаруживается или нет каждая заданная неисправность тестом. При этом нужно брать те тестовые наборы, которые как раз и предназначены для обнаружения заданной неисправности.

Проверка схемы проведена в табл. 18. В соответствующем столбце фиксируется ошибка, сведения для столбцов, расположенных левее, берутся из табл.16, остальные заполняются самостоятельно с учетом введенной ошибки. Полученная реакция сравнивается с эталонной. Таким образом устанавливается, обнаруживается или нет заданная неисправность.

Проверка логической схемы контролирующим тестом Таблица 18
№ набора1 2 3 4 5 6 78 9 10 11 12 13 1415 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

0

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.


Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Математика
История
Экономика
icon
142365
рейтинг
icon
3069
работ сдано
icon
1329
отзывов
avatar
Математика
Физика
История
icon
140128
рейтинг
icon
5849
работ сдано
icon
2647
отзывов
avatar
Химия
Экономика
Биология
icon
94278
рейтинг
icon
2018
работ сдано
icon
1266
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
52 793 оценки star star star star star
среднее 4.9 из 5
ЧКИ РУК
Реферат был сделан очень быстро, буквально за 5-10 минут. Работа была с антиплагиатом, всё...
star star star star star
Самгупс
Конечно текст был чисто из учебников, но приняли хотя бы и на этом хорошо, рада.
star star star star star
Московская международная академия
Работа сделана хорошо, очень высокая оригинальность, рекомендую исполнителя
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

Написать доклад на тему "Принципы организации защищенного документооборота"

Доклад, информационная безопасность

Срок сдачи к 27 мая

только что

задачи

Решение задач, Химия

Срок сдачи к 25 мая

только что

Схема автогенератора с чм

Лабораторная, Радиопередающие устройства, электроника

Срок сдачи к 27 мая

1 минуту назад

Электродинамика

Решение задач, Физика

Срок сдачи к 30 мая

2 минуты назад

КР состоит из 5 разделов

Контрольная, Производственная стратегия, экономика

Срок сдачи к 28 мая

2 минуты назад
2 минуты назад

Расчетные упражнения

Другое, Микроэкономика

Срок сдачи к 31 мая

3 минуты назад

Доработать ВКР

Диплом, безопасность жизнедеятельности

Срок сдачи к 29 мая

3 минуты назад

Правоспособность и дееспособность субъектов...

Курсовая, Теория государства и права

Срок сдачи к 27 мая

3 минуты назад
3 минуты назад

Эссе по литературе

Эссе, Литература

Срок сдачи к 24 мая

3 минуты назад

Выбор системы элементов схемотехнического устройства

Лабораторная, Схемотехника

Срок сдачи к 31 мая

3 минуты назад

"Разработка электронной картотеки" Создать электронную картотеку

Курсовая, программирование на СИ

Срок сдачи к 28 мая

3 минуты назад

помочь и объяснить задания по лабораторным работам

Онлайн-помощь, параллельные методы и алгоритмы, математика

Срок сдачи к 27 мая

4 минуты назад

Курсовая

Курсовая, Веб дизайн

Срок сдачи к 27 мая

4 минуты назад

Ответить на вопросы и решить задачи кратко

Решение задач, административное право

Срок сдачи к 24 мая

4 минуты назад

Электродинамика

Решение задач, Физика

Срок сдачи к 30 мая

4 минуты назад

Пройти тест по английскому

Тест дистанционно, Английский язык

Срок сдачи к 25 мая

5 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

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

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно