Файл: Василенко, Ю. А. Синтез дискретных структур учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.10.2024
Просмотров: 60
Скачиваний: 0
Ю . А. ВАСИЛЕНКО
СИНТЕЗ ДИСКРЕТНЫХ СТРУКТУР
(учебное пособие)
У Ж ГО Р О Д -1973
МЖИСТЕРСТЭО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ УССР
УЖГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Кафедра теоретической кибернетики и математической логики
Ю. А. В А С И Л Е Н К О
С И Н Т Е З Д И С К Р Е Т Н Ы Х С Т Р У К Т У Р
( у ч е б н о е п о с о б и е )
У Ж Г О Р О Д - 1973
Г*с. публичная
и»учно-твхк:і с чая бибЛИО fc- ' ‘.'Г*
ѲКЭЕМШ'Г*' SSM ? ЧИТАЛЬНОГО ЗАЛА
w - / я $ о
Подписано к печати 28.У7.1973.Разрешено к печати 9.07.1973 г.
ББ00837. |
Зк.654. |
|
Тир.ЛЮ . |
|
Форма60 X 84. |
О б 'ем |
9,125 |
пл. |
1/16 . |
|
Пена |
одного |
Экз. |
63 коп. |
Печатная лаборатория УжГУ.г.Ужгород.ул, Горького,46.
- 2 -
Данное учебное пособие возникло на основе использова
ния фрагментов курсов, которые читались автором в Харьков
ском институте радиоэлектроники для студентов специальности
"Электронные вычислительные машины", а также для студентов
Ужгородского госуниверситета / специальность"теоретическая
кибернетика"/.
Четвертая глава написана кан д .тех . наук Н.Я.Какуриным,
а § 2 главы |
ІУ написан Н. Я.іакуриным совместно с А.К.Барино |
вым, который |
выполнил также ряд расчетов на ЭЦВИ "Урал-І4-Д" |
и "Проминь- |
М", потребовавшихся для анализа структур много |
значных дешифраторов и цифровых функциональных преобразова |
|
телей. |
|
В подготовке работы к печати автору оказали существен
ную помощь Д.А.Швец, Е.Р.Дуыницкая, Л.И.Ильина и С.И.Пилюгин.
Ужгород, |
май, 1973 |
Ю.А.Василенко |
Отзывы и |
пожелания просим направлять |
по адресу : |
г . Ужгород, ул. Октябрьская, 54, ауд. 23, кафедра теорети ческой кибернетики и математической логики.
Ответственный |
за выпуск |
ст. преп |
О.Т.Трофимлюк |
3
С О Д Е Р І А Н И Е
ГЛАВА I. Синтез |
комбинационных атоматов |
в неклассических |
|
базисах на основе логического |
дерева |
|
|
§1. О путях минимизации функций в неклассических базисах............ |
4 |
||
§2. Идея метода логического дерева.Самое сложное дерево.............. |
5 |
||
§3. Сложность |
логического дерева. Сходности функции и |
|
|
их вычисления.................................................................................................. |
|
14 |
|
§4. Алгоритмы выбора переданных в вершинах логического |
|
||
дерева . |
.............................................................................................................19 |
||
ГЛАВА П. Частные случаи применения логического дерева.
§1. Использование |
логического дерева для распознавания |
|
|
|||
|
симметричности |
булевых функций............................................................. |
|
35 |
||
§2. Алгоритмы |
минимизации со склеиванием, использу |
|
|
|||
|
ющие логическое дерево . . . . ........................................................ |
40 |
||||
§3. |
Алгоритмы |
минимизации с максимальным склеиванием ...................... |
|
43 |
||
|
0 |
синтезе |
многовыходных схем /К « 2 /.................................................... |
|
58 |
|
ГЛАВА S. |
О блочно-индуктивном методе синтеза логических |
|
|
|||
|
автом атов |
.......................................................................................................... |
|
|
67 |
|
Задачи на применение блочно-индуктивного метода синтеза..................... |
|
85 |
||||
ГЛАВА |
ІУ. |
Синтез |
многозначных узлов дискретной техники. |
|
|
|
§1. Задача синтеза структуры многозначного автомата........................ |
|
86 |
||||
§2. Анализ и синтез многозначных дешифраторов . . . . . . . |
. |
90 |
||||
§3. |
Многозначные цифровые функциональные преобразо |
|
|
|||
|
ватели ............................................................................................................... |
|
|
|
ІІ6 |
|
§4. |
Синтез микропрограммных ав то м ато в ............................................... |
131 |
||||
ЛИТЕРАТУРА...................................................................................................................... |
|
|
|
14* |
||
|
|
|
|
|
|
|
- |
|
|
ч |
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Г |
Л |
А |
В |
|
А |
|
I |
|
|
|
|
|
|
|
||
|
СИНТЕЗ |
К01ШИНАНИОННЫХ |
|
АВТОМАТОВ |
В |
НЕКЛАССИЧЕСКИХ |
|
|||||||||||||||
|
БАЗИСАХ НА ОСНОВЕ |
|
|
ЛОГИЧЕСКОГО |
|
ДЕРЕВА |
|
|
|
|||||||||||||
I |
I . |
О |
ПУТЯХ МИНИМИЗАЦИИ |
|
ФУНШЙ |
В |
НЕКЛАССИЧЕСКИХ |
БАЗИСАХ |
||||||||||||||
|
Задачи комбинационного синтеза в таких базисах, как |
стрелка Пир |
||||||||||||||||||||
са, |
штрих Шеффера и некоторых других,, |
нередко решает в два |
этапа: |
|||||||||||||||||||
|
I / |
синтез |
в базисе |
|
|
♦ |
|
«• |
, |
|
— |
fr |
|
|
|
|
|
|||||
|
л |
« |
, |
* |
V |
* |
I |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
. * V |
|
|||
|
2 / |
переход |
по |
соответствующим формулам от |
базис» «<£ |
, *— |
||||||||||||||||
к используемому |
базису. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
При этом на первом этапе использует такие известные методы ми |
|||||||||||||||||||||
нимизации функций алгебры логики как метод |
неопределенных коэффици - |
|||||||||||||||||||||
ентов, метод Хвайив-Йак-Класки, |
метод Блейка-Порецкого, метод логичес |
|||||||||||||||||||||
кого |
дерева и другие. |
|
р Л |
|
|
/• |
|
|
** |
|
|
|
|
|
|
|||||||
|
Переход от |
базиса |
¥ |
— |
к базису |
штрих Шеффера осно- |
||||||||||||||||
|
<* |
, |
, |
|
||||||||||||||||||
ван |
на |
тождестве / 3 |
/ |
* |
|
|
t, |
|
*t |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
X |
,f, |
V Я ft |
|
|
* |
|
Ar t |
|
f, У t ((**&■)*ft, ), |
|
|
||||||||
где |
* |
- |
символ операции штрих Шеффера. |
Переход к другим |
базисам |
|||||||||||||||||
ооиован на аналогичных тождествах; |
например, |
для |
базиса стрелка |
Пир |
||||||||||||||||||
са /операция Вебба/ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
x f t |
V 2 Уж ш ( ( о ф х ) i f , ) é ( х t f g ) , |
|
|
||||||||||||||||
где У- символ операции стрелка Пирса; |
для |
базиса Іегалкина с |
опера |
|||||||||||||||||||
циями |
<£ |
и |
© |
/сложение |
|
по модулю 2 |
/ |
|
|
|
|
|
|
|||||||||
|
|
|
v x |
f t |
т |
x |
f i |
« |
|
|
|
|
|
|
, |
|
|
|
|
|||
Кроме этого пути минимизации функций |
|
в неклассических базисах ; возмо |
||||||||||||||||||||
жен еще один путь: |
это |
минимизация функций в |
данном неклассической |
|||||||||||||||||||
базисе |
с использованием характерных свойств и специфик операций дан |
|||||||||||||||||||||
ного |
базиса, |
|
|
|
|
|
|
|
|
|
' |
|
|
|
|
|
|
|
|
|
||
|
В работе [Ь] |
рассматриваются некоторые |
вопросы минимизации |
|||||||||||||||||||
переключательных функций |
в шеФферогой и |
Пирсовой |
алгзбрах. |
|
||||||||||||||||||
|
|
5 |
- |
|
|
Шефферовой /Пирсовой / |
алгеброй называется совокупность |
I Р „ М , л |
|||
где Р ~ |
множество переключательных функций, а М г - |
множество, |
|||
над элементами которого |
задана операция штрих Шеффера /Стрелка Пирса/ |
||||
Процесс получения минимальных форм переключательных функций |
|||||
в Шефферовой /Пирсовой/ |
алгебре состоит |
из двух этапов. |
На первом |
||
этапе находятся все простые импликенты заданной переключательной |
|||||
функции или, что фактически |
то же самое, |
ее сокращенная Шѳфферовая |
|||
/Пирсовая/ нормальная форма. |
|
|
|
||
На |
в^ом этапе ищутся приведенные |
системы простых имплицант, |
|||
строятся тупиковые нормальные формы, из числа которых отбираются ми нимальные. ■
При этом используются такие законы, |
как закон поглощения / в |
|||
Шефферовой алгебре/: |
|
|
||
( X t і ( х , * х г ) ) ~ (x t Н * а * х л |
* > , |
|||
закон полного |
склеивания: |
|
|
|
' f f ( x t |
) t |
( x t * Х г + (Хл фХа ) ) ) ъ ( ( Х € # х л ) |
||
и другие. |
|
|
|
|
§ 2. |
ИДЕЯ |
МЕТОДА ЛОГИЧЕСЕОГО |
ДЕРЕВА. САМОЕ |
|
|
|
СЛОІНОЕ |
ДЕРЕВО. |
|
Метод логического дерева для минимизации функций булевой ал-
гебры |
в классическом |
базисе |
А |
, |
* |
~ |
# |
|
7 J |
|||
& |
У , |
описан в работах [в, |
||||||||||
|
Напомним, что основывается метод логического дерева на фор - |
|||||||||||
муле |
разложения функции f |
по ее |
существенной |
переменной X |
, |
|||||||
например |
, |
по |
|
; |
|
|
|
|
|
|
|
|
f |
f |
* |
/ |
, |
fa,ъ . |
о-л ) ^ |
f |
r o |
, * , , Ѵзьі/ц |
|
||
Графически это разложение изображается так:
6
|
|
Рис. I |
|
|
|
|
|
|
|
|
|
|
Функции |
ftO .K * ,...,# * ) |
И |
f ( 1 , -Xj, |
|
X„ ) |
f |
в свою очередь J |
|||
можно разложить по их существенных переиенных по фориуле |
/ I / . |
|
|||||||||
|
Если же функцию |
х *. |
рассматривать в базисе |
штрих |
|||||||
Шеффера, то граф на рис.І |
изображает разложение |
функции |
/л * * , |
.,ф |
|||||||
по формуле |
|
|
|
|
|
|
|
|
|
|
|
|
|
... /2/ |
|
|
|
|
|
|
|
|
|
где |
f t - f( o t агг ...... sen ) |
и |
f t - f / / , ^ |
, |
..., |
|
|
|
|
||
|
В базисе стрелка Пирса /операция Вебба/ |
граф на рио.І изобра |
|||||||||
жает |
разложение функции |
f( Z t , |
,.v a r j |
по формуле |
|
|
|||||
|
f (* t. |
|
* f i ) t ( t o * x t ) t £ ) t |
|
/3 / |
||||||
а в базисе Кегалкина по формуле |
|
|
|
|
|
|
|
||||
|
|
|
|
|
® |
* t f 2 . |
' |
/Ѵ |
|
||
|
В формулах / 2 / . / 3 / |
и / ц / |
переменная |
X . |
считается |
существен- |
|||||
|
|
|
|
|
|
|
* |
|
О • |
|
|
ной переменной. Аналогично разложение можно производить по лобок |
|||||||||||
существенной |
переменной |
X - . |
|
|
|
|
|
|
|
|
|
'jr |
Рассматриваем базис |
штрих Шеффера. |
В этом базисе граф вида |
||||||||
|
|||||||||||