Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Общие положения. При разработке ДУ обычно возникает задача оптимизации их структуры, т.е




МИНИМИЗАЦИЯ ФАЛ

 

При разработке ДУ обычно возникает задача оптимизации их структуры, т.е. получения экономичной и надежной технической реализации [2, 3]. Это означает, что из двух схем ДУ, выполняющих одинаковые функции, следует выбирать ту, которая содержит меньшее число элементов, а при одинаковом числе элементов – ту, суммарное число входов используемых элементов которой будет наименьшим.

Решение этой задачи связано с проблемой минимизации (упрощения, сокращения) ФАЛ, реализующих данное ДУ.

Минимизация – это процесс нахождения такого эквивалентного выражения ФАЛ, которое содержит минимальное число вхождений переменных. При минимизации могут быть различные варианты: получение выражений с минимальным числом инверсных переменных либо с минимальным числом вхождений какой-либо одной переменной и т.д.

Для минимизации функций и поиска наиболее экономичной схемы, реализующей заданное выражение, до сих пор не найдено эффективных алгоритмов, позволяющих решать эти задачи целенаправленно и быстро. Гарантированно найти минимальное выражение для произвольной функции можно лишь методом полного перебора вариантов различных способов группировки в процессе минимизации, а это реально осуществимо лишь при небольшом числе аргументов. С ростом их числа сложность минимизации и поиска экономичной схемы растет экспоненциально и очень скоро становится не под силу ни человеку, ни ЭВМ.

С точки зрения подходов к упрощению логических выражений функции, с которыми имеет дело схемотехник, удобно разделить на три группы: функции малого числа аргументов; «объективные» функции многих аргументов и «субъективные» функции многих аргументов.

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

Ко второй группе – громоздких «объективных» функций – относятся функции более пяти переменных, которые были получены не человеком, а отражают некую объективную природную зависимость. Для этих функций характерно следующее. Во-первых, в них не заложено какой-либо простой логической закономерности, которую можно угадать и использовать для минимизации, т.е. таблица такой функции это просто некая случайная последовательность единиц и нулей. Во-вторых, в силу значительного числа переменных полный перебор вариантов при любом способе поиска минимальной или любой другой экономичной формы практически неосуществим. И, в-третьих, что самое важное, из теоремы О.Б. Лупанова об оценке сложности функций следует, что с ростом числа аргументов доля экономичных по оборудованию функций стремится к нулю, т.е. почти все функции оказываются неупрощаемыми. Следовательно, задача поиска минимальных форм «объективных» функций многих аргументов не только сложна и громоздка, но и с большой вероятностью безнадежна. Это учитывают изготовители элементов, выпуская для реализации функций многих переменных специальные микросхемы – программируемые логические матрицы (ПЛМ) и постоянные запоминающие устройства (ПЗУ). При использовании наиболее распространенных простых вариантов ПЛМ реализация функций будет самой экономичной по затратам аппаратуры, если функция приведена не к минимальной, а к кратчайшей форме. Если же при минимизации ДНФ самую короткую форму получить не удалось, то проигрыш оказывается небольшим, поскольку стоимость реализации на ПЛМ каждой элементарной конъюнкции ДНФ невелика – 1/50 стоимости корпуса. Одной из целей освоения промышленностью ПЛМ как раз и была экономия труда разработчиков схем.

При использовании ПЗУ на них реализуется непосредственно ТИ функции, т.е. ни записи ФАЛ, ни тем более ее минимизации не требуется вообще.

К третьей группе – «субъективных» функций многих аргументов ‑ относятся функции, составленные человеком. Особенность их связана с понятием декомпозиции. Это значит, что сложная ФАЛ разбивается на более простые составляющие, из минимальных форм которых в конечном итоге строится аппаратная реализация ДУ. Однако декомпозиция может быть выполнена неудачно, и устройство в результате будет неэффективным. Для того чтобы избежать этого существуют специальные методы декомпозиции, которые позволяют получать приемлемый результат.

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

Если значение ФАЛ однозначно определено на всех возможных наборах значений ее аргументов, то она называется полностью определенной (заданной). Если же на некоторых наборах значение функции является безразличным и однозначно не определено, то такая функция называется неполностью или частично заданной.

В соответствии с этим разделим и методы минимизации (упрощения) ФАЛ на две группы: методы минимизации полностью заданных ФАЛ и методы минимизации неполностью заданных ФАЛ.

 




Поделиться с друзьями:


Дата добавления: 2015-07-02; Просмотров: 471; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.