Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 72
Текст из файла (страница 72)
как системы логических функций; 4) реализация системы канонических уравнений схемой в функционально полном базисе. Число элементов задержки определяется на этапе 3, число логических элементов— на этапе 4. Эта схема сыграла большую роль в развитии методов синтеза автоматов. Однако, как показал 30-летний опыт, надежды на ее широкое практическое использование оказались сильно преувеличенными, Это объясняется в основном следующими причинами. Во-первых, как было установлено ранее, схемы с й элементами задержки имеют 2» состояний, поэтому описание сколько-нибудь больших схем в терминах состояний и таблиц переходов оказывается довольно громоздким.
Во-вторых, на разных этапах решаются разные задачи минимизации, которые плохо связаны 846 между собой. Известны примеры, когда уменьшение числа состояний приводит к усложнению логики схемы. Крома того, различные варианты кодирования (для й задержек существует (2')! вариантов) приводят к разным системам канонических уравнений; предвидеть сложность их реализации заранее, на этапе кодирования, невозможно.
Поэтому в практике получают все большее распространение методы, обходящие каноническую схему синтеза. 84. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИИ И АВТОМАТОВ Представление автомата схемой из элементов — это исторически первый и наиболее исследованный вид структурной реализации автомата. Другой ее вид — реализация автомата программой. Здесь мы ограничимся вопросами программной реализации комбинационных логических автоматов, т. е. систем логических функций.
Под программой будем понимать пронумерованную последовательность команд Ьь ..., Ь„взятых из некоторого фиксированного набора (системы команд). Программа работает над конечным множеством пронумерованных (или проименованных) двоичных ячеек. Номер (или имя) ячейки называется ее адресом; именем ячейки часто будет служить имя логической переменной, значения которой хранятся в этой ячейке. Система команд содержит команды-операторы вида Ь:= =/(аь ..., ар) (выполнить операцию / над содержимыми ячеек а, ..., ар и результат положить в ячейку Ь) и двух- адресные условные переходы двух видов: 1) «если а, то 1, иначе /» (если а=1, то перейти к выполнению команды Ь;, иначе перейти к Ь,); 2) «если а(а=О), то 1, иначе /». Операция /(а„..., ар) — это логическая функция р переменных; в частности, оиа может быть константой О или 1. Если /— номер следующей команды, то переход можно считать одиоадресным: «если а, то 1 (иначе перейти к следующей команде)», а если 1=/, то безусловным: «перейти к 1».
Любая из команд указанных типов может быть заключительной, что указывается словом «конец». Процессом вычисления программы Ьп ...,й, называется последовательность шагов Ь(1), й(2), ..., Ь(1), на каждом из которых выполняется одна команда программы. Эта последовательность определяется так: 1) Ь(1) =й~', 2) если Ь(1) = =й, — оператор, то й(1+ 1) =Ь,+и 3) если й(1) — условный 342 переход, то номер команды А(!+1) указывается этим переходом; 4) если АЯ вЂ” заключительная команда, то процесс вычисления останавливается после ее выполнения. Число 1 называется временем вычисления.
Программа П вычисляет (или реализует) логическую функцию ! (хь ..., х ) =у, если для любого двоичного набора а= (о!, ..., а,) прн начальном состоянии памяти х!=а!, хз=ам ..., х,=а„(состояние остальных ячеек несущественно) программа через конечное число шагов останавливается и при этом в ячейке у лежит величина ) (о!, ...,а ). Если под сложностью схемы, реализую!цей автомат, обычно понимается число элементов в схеме (см.
$ 8.3), то сложность программь! можно понимать в различных смыслах: 1) число команд в тексте программы; 2) объем промежуточной памяти, т. е. число ячеек для хранения промежуточных результатов вычислений; 3) время вычисления, которое будет характеризоваться двумя величинами: ! средним временем г,р(П) = — „', "',тг(о) и максимальным 2« временем 1 „,(П) =шахте(о), где сумма и максимум бе« рутся по всем 2" двоичным наборам о, а тг — время работы программы П на наборе а.
Любой схеме, реализующей функцию ! и содержащей М элементов, нетрудно поставить в соответствие программу, реализующую 1 и состоящую из У команд, следующим образом. Занумеруем элементы схемы числами 1, 2, ..., п так, чтобы на любом пути от входа к выходу номера элементов возрастали; при этом номер 1 получит один из входных элементов, а номер Ж вЂ” выходной элемент. Пусть элемент ьч схемы реализует функцию !р! и ц его входам присоединены выходы элементов ел, ..., е! (некоторые из ннх, возможно, являются входами схемы).
Поставим элементу е! в соответствие либо ячейку а! и команду а~=йп(ал, ... ..., ау ), если 1Ф У; либо ячейку у и команду «у: = =<рУ(а!!, ..., а; ) конец», если !=У. Получим програ!лму, не содержащую условных переходов (такие программы будем называть операторными), в которой порядок команд в точности соответствует нумерации элементов в схеме, а система команд — базису схемы.
Проблемы синтеза операторных программ в основном сводятся к проблемам синтеза схем: в частности, вопросы функциональной полноты системы команд и минимизации 348 собственного текста операторной программы совпадают соответственно с задачами о функциональной полноте системы функций и о минимизации схем. Поскольку операторная программа не содержит условных переходов, время ее вычисления на любом наборе одно й то же; отсюда г„„= =(„=У, т. е.
оба вида временной сложности совпадают со сложностью текста программы и, следовательно, в силу теоремы 8.!3 при достаточно больших и почти для всех функций близки к 2"/и. Наоборот, проблема минимизации памяти (за счет многократного использования одной ячейки для нескольких промежуточных результатов) для операторных программ является нетривиальной комбинаторной задачей. Другой «крайний» вид программ, вычисляющих логические функции, — это программы, состоящие из команд вида у:=о (о=О или а=!) и условных переходов. Такие программы называются бинарными программами.
Всякую булеву формулу Р, содержащую У букв, можно реализовать бинарной программой, вычисляющей г за время !»«,~=У и содержащей !Ч команд условного перехода (а также две команды у:=0 и у:=1, которые в оценках не учитываются). Для описания метода реализации используем представление программы в виде графа (в котором вершины соответствуют командам, а ребра — переходам).
Пусть 6~ — граф программы для функций ~~ с начальной вершиной ом и двумя заключительными вершинами ом (с коман- 1 дой «у=О») и щ, (с командой «8=1»); 6, — граф программы для 1«с началом ою и концами оз, и ом. Тогда: 1) проо грамма, граф 6 которой получен присоединением 6з к «нулю» 6~ (т. е. отождествлением вершин ом и ою, команда в «у:=0» при этом отбрасывается), вычисляет функцию 1= =~~~/1з, 2) программа, граф 6' которой получен присоединением 6» к «единице» 6~ (отождествлением ом и ом), вычисляет )=~,Щ; 3) программа, граф которой получен о из 6~ заменой команд в ом и ом на инверсные («у:=0» на «йч=1» и наоборот), вычисляет 1ь Заметим, что в графе 6 получаются две единичные, а в графе 6' — две нулевые заключительные вершины.
В обоих случаях их надо отождествить. Пример 8.11. Формула (х,~/х») (х»«4~/х») реализуется бинарной программой, граф которой приведен на рис.8.17. Описанный метод не гарантирует минимальность получаемых программ по времени и числу команд. Существуют 949 другие методы, которые, в частности, для любой функции и переменных дают бинарную программу с 1„„,(п независимо от длины исходной формулы.
В общем же случае сложность бинарных программ характеризуется следующими асимптотическими оценками. Пусть Ев (и) — функция Шеннона для числа команд бинарных программ (см. аналогичное определение для Ех ('а) в конце $8.3). 2и Теорема 8.14. 1) Ев ('и) —, причем существует метод и синтеза бинарных программ, удовлетворяющих этой оценке, длЯ котоРых 1иакс и; 2) длЯ любОГО 6)0 дОлЯ фУнк2и ций, для которых: а) Ев(1)и '(1 — е) —;б) 1ир())((1 — е)п, и стремится к 0 при и-+.со. П. Таким образом, сложность бинарных программ, вычисляющих логические функции, по числу команд асимптотически равна сложности операторных программ.
Однако бинарные программы обладают двумя важными достоинствами, которых нет у операторных программ. Первое из них— это отсутствие промежуточной памяти в процессе работы программы. Оно связано с тем, что команды условного перехода обращаются только к значениям входных переменных, которые ие меняются в процессе вычисления; новых же значений переменных этн команды не создают. Это позволяет реализовать бинарные программы на постоянной па- Т' ти. Второе достоинство бинарных программ — более выс кое быстродействие, т.е. меньшие величины 1„,„, и 1 р.
Напомним, что для операторных программ 1и,„,=1„=М. Для времени вычисления бинарных программ справедливы следующие утверждения. 350 1. Для любой функции г, существенно зависящей от всех а переменных, 1!одр и+11(Г, (~) ~и, причем обе границы достигаются. 2. Существуют последовательности функций 11(х1), Гр(хь хг), .-~ (л(хп -.~ хл)-., для которых 11П1 глр(~л) =2; инар ~о че говоРЯ, с Ростом п 1,р(1 ) пРактически нЕ УвеличиваЕтсЯ, Примером такой последовательности является любая последовательность ~ь -., Гл-., где 11=хо-., Гл+1 = хл-нО~л (Π— дизъюнкция или коныонкция). 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
