Савельвев А.Я. Основы информатики

Подождите немного. Документ загружается.

10.8 Реализация частотно-минимального метода

Сравниваем l-io и 6-ю строки:

Сраниивасм

l-io и

7-ю строки:

равиивасм 2-и)

1-юс|роки;

Сранмивасм 2-io

4-io строки:

Сранпивасм 2-!о

5-fo строки:

С ранинвасм 2-1о

6-to строки

{ равпивасм 2-to

7-10 cipoKn:

Сравниваем

3-KI

4-ю строки:

{•равмивасм

З-то

5-io строки:

( равмивасм З-ю

6-!о строки:

Сравниваем

3-ю и

7-ю строки:

0021 т=1

2011

0021 №=1,№=1.

1021 ет(1) = 6,

1Y=|2021.

0021 ;л =

з,

1012

2001 № =

0012

2001 /Д=2.

2010

2001 W=l,№ = 3.

2011 Щ2) =

2001 /Л

=2.

1021

2001 /« =

1012

0012 /Л =

2010

0012 №=2.

2011

0012 «=3.

1021

0012 «=1, /Л =

1012 Щ3) =

2021

IY= 2021 ,

2012

as:

Методы логического проектирования

Сравниваем 4-ю и 5-ю с1роки:

2010 /R = ],m =

4,KR(4)

= 5.

2011

2021

2012

Сравниваем 4-in и 6-ю шроки

Сравниваем 4-ю и 7-ю строки:

Сравниваем

5-KI

6-Ю

cipoKM:

Сравниваем 5-i<) и 7-!о строки:

Сравниваем 6-ю и 7-ю строки:

Признак Ry =\, матрица ITERM пуста.

PaccMtrrpHM мафицу IY.

Сравним 1-ю

2-юсгроки:

2010

1021

2010

Г012

1021

2011

1012

1021

1012

;л

т^2.

;л

« =

2021 № = 0,

2021

Сравниваем 2-io и 3-ю строки:

2021 m

2,RV=0.

2012

Терм 2021 является минимальным, его записываем в матрицу ITERM. Сравниваем З-ю и

4-IO строки:

2012 ;я = 0.

2012

120211

ITERM

2012

6. Формируем матрицу IQ:

7. Получаем матрицу IFSTR:

,101101

IFSTB

258

lO.S-

Реализащт частотно-минимального метода

8. Получаем матрицу IFSTB:

101101

011011

112011

100101

011011

111112

/„ = /;, = /i4=/i6;

/и </„;/,,-^44;/,,</»-

И i

Mil!

рми!.1

4} вычеркиваем 3-Й и 6-й столбцы,

также 4-й-

Ич iQ. В1.1черки»аем 5-й сюдбеи,

9. Получаем новую мафицу:

П мипима.1Ы!0С покрытие вошли сермы 2021,

2012.

Ответ. pcj\Jibiai в базисе Вебба: {х^

4-(JTJ

'i-0))4-(j(2 ^{^А

0)). в базисе Шеффера:

((b/l)/x,)/((x./l)/v,).

259

1J. ЛОГИЧЕСКОЕ ОПИСАНИЕ И АНАЛИЗ

ЭЛЕКТРОННЫХ СХЕМ

ИЛ.

Логические операторы электронных схем

Но зависимости выходного сигнала от входного все электронные схе-

мы [7. 17J можно условно разбить на:

cxeAfbi первого рода, содержащие комбинационные схемы, — схемы,

выходной сигнал в которых •зависит только от сосюяния входов {наличия

входных сигналов), в каждый момент времени;

схемы второго рода, содержащие накапливающие схемы (элемен-

ты с памятью)^— схемы, выходной сигнал в которых зависит как от

входных сигналов, так и от состояния схемы в предыдущие моменты

времени.

По количеству входов и выходов схемы бываю!: с одним входом и о/{-

ним выходом, с несколькими входами и одним выходом, с ощшм входом и

несколькими выходами, с несколькими входами и выходами.

По способу осуществления синхронизации схемы бывают: с внешней

синхронизацией (синхронные автоматы) и с внутренней синхронизацией

(асинхронные автоматы являются их частным случаем).

Практически любая ЭВМ состоит из комбинации схем первого и вю-

рого родов разной сложности.

Рассмотрим некоторые конкретные примеры.

На рис. 11.1,« показана принципиальная электрическая схема, выпол-

ненная на транзисторе.

Схема работает следующим образом. В интервале времени от () до /,

(рис.

11.1,6) на входе действует почти нулевое напряжение. За счет дeJrиle-

ля Я1-Я2 и источника Е^ транзистор ПТ\ закрыт и на выходе на1!ряжение

равно - £'^. В момент /j происходит изменение напряжения на входе (те-

перь действует f/j), что изменяет ток в транзисторе ПТ\ до такой cierreun,

что транзистор открывается. Через резистор R^ течет ток, который изменя-

260

//. /. Логические операторы электронных схем

ет напряжение на выходе: оно становится близким нулю . Так продолжает-

ся до момента ^21 когда состояние на входе снова изменяется, вызывая со-

отвегствующее изменение на выходе. На рнс. 11.1,6 показана временная

диаграмма изменений состояний на входе и выходе схемы. Напряжения на

выходе принимают два значения (высокий уровень — О, низкий уровень —

1).

Тогда логически работу рассмотренной схемы можно описать с помо-

щью функции НЕ (рис. 11. I, в), что подтверждается следующим:

0-'| 'l-'2 '2-')

О 1

О I О

Момет нремеми ,

И\ол

Пыхол

ii t.

О \ I \ О t

"'l I

ГП

( oil '

Рис.

i.i. Элементарная электронная схема

Логический оператор схемы — элементарная логическая функция, с

помощью которой описывается работа схемы.

Таким образом, рассмотренная выше схема описывается функцией НЕ

и называется инвертором (рис.

11.1,

в).

На рис. 11.2, а показана схема днзъюиктора, описываемая логическим

оператором ИЛИ (рис. 11.2, в). Временная диаграмма работы этой схемы

представлена на рис. 11.2, б.

На рис. 11.3, а показана комбинация электронных схем дизъюнктора и

инвертора, выпо;гне1шая на транзисторах, а ее логический оператор ИЛИ—

[\Н — на рис. 11.3, е. Временная диаграмма работы этой схемы дана на

рис.

11.3,

б.

Ана1югичным образом проводится анализ работы схемы конъюнктора

(рис.

11.4, а). Временная диаграмма работы схемы н ее логический оператор

представлены на рис. 11.4, б, е. Основной особенностью этих схем является

Здесь состояния схемы кодируются следующим образом: состоянию «i» соответствует

больший по модулю отрицательный потенциал, а состоянию «О» — близкий к «О» потенциал

(положительная лотика).

261

/ / Логическое описание и анализ электронных схем

то.

что они идентичны схемам, показанным на рис. 11.2, а и 11.3, а, но при

отрицательной логике кодирования, т. е. состоянию «1» соответствует высо-

кий потенциал, состоянию «О» — низкий потенциал. Этим лишний раз под-

тверждается справедливость законов де Моргана, которые описывают двой-

ственный характер наборов логи-

ческих функций И—НЕ и ИЛИ—

НЕ

(рис.

11.5,

а,

б,

в).

Sx,

дг

•М-

вх,

Вых

Ал,

^С^Лг)

*а-

На основании вышеизложен-

ного можно ирийги к заюгюче-

нию,

что различные электронные

схемы или их комбинации на ло-

гическом уровне могу

быть опи-

саны с помотыо логических

операторов. Такое операторное

описание электронных схем по-

зволяет абстрагироваться ог фи-

зической природы конкретных

электронных элементов и осуще-

ствлять их анализ. При этом оказывается, что для анализа совсем не обяза-

тельно иметь саму схему. Для того чтобы получить значение функции на

выходе какой-либо схемы, достаточно записать эту зависимость п виде ло-

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

мой функцией.

Рис.

ii.2. Схема лизъюнктора

ij ь_г is tj_

1ЛГТГТ

Рис.

И.З. Схемадшъюикторас инверсией

/ / / Логические операторы электронных схем

' ' ' • • • 11

|дл^,,х,)

=кп№

Рис.

11.4. Схема коньюнктора

Для аишгиза электронных схем с помощью аппарата алгебры логики

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

При -)1ом ИСХОДЯ1 Hi 10Г0, что каждому функциоиальгюму элементу элек-

тротюй схемы можно поставить в соответствие логический оператор. Этим

самым устанавливаегся однозначное соотвегствие между элементами схе-

мы и ее магематическим описанием.

Рис.

i 1.5. Схема коиъгоиктора с инверсией

Anajm i электронной схемы проводится в два этапа:

1)иг гфиншпшальной схемы удаляются все несущественные вспомо-

raiejii,in>ie элементы, которые не влияют на логику работы схемы;

2) через логические oiiepaTopbi выражают все элементы, получая логи-

ческое уравнение, которое является моделыо функции, выполняемой за-

данной схемой. Проводится анализ этой функции с целью устранения лиш-

них ч<1С1ей-

263

/ / Логическое описание и анализ электронных схем

Рис.

11.6.

Логическая схема с

двумя выходами

Например, схема, представленная на рис. 11.6, может быть описана ло-

гическими выражениями у^

х^ ; у2 =х^

XjX,

•

Однако с точки зрения

инженерного проектирования чаше прихо-

дится решать обратную задачу, называе-

мую задачей синтеза электронных схем.

Задачу синтеза электронных схем

можно сформулировать следующим обра-

зом: при заданных входных переменных и

известной выходной функции спроекти-

ровать логическое устройство, которое

Xj 1| I I I реализует эту функцию (при этом могут

~1 I I' I—- быть наложены дополнительные ограни-

чения либо в виде системы исиользую-

г—1 щихся логических элементов, либо в виде

_11 I требований по количеству логических

операторов). Следовательно, в результате

решения задачи синтеза возникает логи-

ческая схема, воспроизводящая заданную

функцию.

Обычно, решая задачи анализа и синтеза, используют полные базисы

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

поставляют с некоторым физическим элементом. Значит, логическую

схему можно заменить структурной схемой, состоящей из физических

элементов.

Таким образом, удается соединить математическую задачу снигеза ло-

гической схемы с инженерной задачей проектирования электронной схемы.

Прн разработке электронной схемы за основные критерии принимают ми-

нимум аппаратуры, минимум типов применяемых элементов, максимум

надежности.

С точки зрения математической логики задача синтеза решается при

обеспечении минимального числа логических операторов, минимального

количества типов логических операторов. Можно сформулировать гюсле-

довательно решаемые задачи прн синтезе электронной схемы:

составление математического описания (системы логических уравне-

ний),

адекватно отображающего процессы, происходящие в схеме;

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

каждой из них в заданном базисе;

переход от логических уравнений к логической (структурной) схеме

посредством применения логических операторов.

264

112 Электронные схемы с одним выходом

Проблема синтеза наиболее подробно исследована для конечных авто-

матов, а для бесконечных автоматЬв в большинстве случаев она имеет лишь

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

заданы условия функционирования автомата. Чем выразительнее язык за-

дания (т. е. чем он удобнее для заказчика), тем сложнее метод синтеза.

Син-

тез абстрактных цифровых автоматов — один из этапов синтета автоматов,

заключающийся в построении абстрактного автомата (например, его табли-

Ubi переходов и выходов) по одному из способов задания отображения

«вход—выход», которое должен реализовать этот автомат. Другими слова-

ми,

с помощью процедуры синтеза происходит переход от описания авто-

мата на начальном языке к описанию его на автоматном языке. Этим во-

просам посвящена глава 12.

.2.

Электронные схемы с одним выходом

Схемы с одним выходом и несколькими входами относятся к наиболее

простым схемам. Основная сложность при синтезе этих схем состоит в том,

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

Пример 11.1. Сиигезировать схему в базисе «НЕ-инпликация», если функция имеет вид

1't; И! о ii II с ilcpeiijicM oi смешанной

сис1смы лотческич функ(шй к системе «НВ-

нмилмкаиия» fia основе правил перехода:

\_..L_

- (11,1)

Рис. Ii,7. Логическая схема иа

элементах импликации и инверсии

к примеру 11.1

Получим ф( tp Yj. .г,) " -Х| -+

(J:,

^ J:, "^

Фумкиин <p(v,, .V;,-X,) может быть реа-

лн (онаиа на основе логических операторов

сП!:» и «импликация» (рис- 11,7),

Ответ-

ло1

ическая схема на рис. 11,7.

Задача синтеза, как правило, имеет различные решения в зависимости

ш выбранной системы логических элементов. Однако для любой заданной

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

вегствующую этой функции. Получение схемы с минимальным количест-

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

ции алгебры логики.

265

/ / Логическое описание и анализ

эле/

~npouiibix

схем

Некоторые более сложные схемы, имеющ|*:; несколько выходов, могут

быть сведены в частном случае к набору схем с одним выходом. Тогда

син-

тез осуществляется путем декомпозиции для аждой вь!деляемой схемы.

Рассмотрим в качестве примера синтез однора |рядного двоичного сумма-

тора методом декомпозиции.

Пример 11.2. Стпезировагь схему, залатгую шблице 11.1, в базисе И-ПЛИ-ПЕ

Таблица II 1

", 1

(]

..^\

II,

ряда:

, Ь, •—cjiaiacMNC i-i о разряда операндов « и / с, - - сумма слз!аемы\ ;-!о раз-

I — соотетсгветю iiepettocM wi /-го и (('-

)-# разрядов.

Ре

1М

е и ие Синтезируемую схему можно рассматрин^гь как схему, состоят) к> m лн\ х

час1ей:

схемы для получения поразрядной суммы с, (полу ,умма1ор) и схемы для получения

переноса и, ;

На основе leopeMi,! (И) 20) мнитем С11/1Ф для

1|)умкци

.г, и ri,

Используя МИ1 имизиругошие карты Карио, по-

лучаем минималы ые формы для каждой п! ([)упк-

НИИ с, и и, (рис.

/1,8,

о.

б):

(11 2)

bj ni;

Рис.

i.8. Минимизация функций

с, и п, к примеру 11.2

jc-= n,_iia,h,

+.i,h,)+

и, i(a^h, +a,h,}.

[ri,

= и,_,((7, +1 ,} + aJ^,.

Функции (П.;*) м<)1>1 быть реалуцонапы схе-

мой,

яредсгавлен1г

1й

на рис. !

Ответ: логич* кая схема па рис I 1-9,

Однако способ решения задачи, который i* оказан в примере 11.2, не

всегда дает минимальное peujenne. Например, г^ входное выражение лля с,

может быть записано иначе. Из таблицы

11.

[ ви^ но, что поразрядная сумма

с, равна единице тогда, когда одно из слагаем1|(х а,, й, или перенос ti,,,

равен единице, а остальные слагаемые равны,<:нул1о и при этом п, -О

(п,

=^1) или когда все три слагаемых рлвны единице. Поэтому

с, =(а^ +

Ь^

+ п,„|)п, +i3,Z>,n,_|.

266