Аннотация:В настоящее время электроника находит применение во многих областях техники и жизнедеятельности человека. В основу работы многих управляющих систем положены сверхбольшие интегральные схемы (СБИС). При создании интегральной схемы требуется реализовывать системы частичных булевых функций. Хотя современные технологии и объёмы производства микросхем позволяют выпускать очень большие кристаллы, тем не менее, площадь кристалла всегда пропорциональна проценту получаемого брака и трудоёмкости самого процесса изготовления кристалла. Поэтому существует задача уменьшения площади кристалла конкретной СБИС. При реализации комбинационно-логических схем на регулярных двухуровневых структурах (программируемые логические матрицы, ПЛМ) данная проблема сводится к задаче минимизации д.н.ф. системы частичных булевых функций.
В настоящей работе сделана попытка развить известный метод «Листопад», который широко применялся при синтезе отечественных СБИС до начала 90х гг. прошлого века на предприятиях Министерства электронной промышленности СССР в подсистемах логического синтеза нескольких систем автоматического проектирования (САПР СБИС). Усовершенствование данного метода шло по пути разработки эвристик, применяемых при ветвлении алгоритма, включающих использование методов принятия решений на основе прецедентной информации.
Полученный алгоритм минимизации реализован в виде программы на языке С++. Исследованы результаты работы программы на разных примерах входных данных. Получены данные по оптимальным настройкам использованных алгоритмов. В процессе создания программной системы были предложены несколько дополнительных эвристических методов, способствующих повышению качества минимизации д.н.ф. На основе результатов работы программы на множестве примеров проведено исследование по настройке алгоритма для разных типов задач. Даны подробные описания использованных алгоритмов.