ИСТИНА

В заявке на грант были сформулированы следующие цели. Будут развиты созданные ранее и предложены новые эффективные методы синтеза схем для "типичных" и самых "сложных" функций алгебры логики в ряде "традиционных" моделей дискретных управляющих систем с определенными ограничениями на структуру и параметры схем. С помощью этих методов для сложности указанных функций в некоторых классах схем (контактных схем с различными ограничениями на смежные контакты, предикатных схем в ряде базисов и др.) будут получены асимптотические оценки, имеющие, как правило, высокую степень точности. Кроме того, будет установлена возможность реализации указанных функций схемами из некоторых классов, оптимальными как по сложности, так и по задержке на уровне оценок высокой или близкой к ней степени точности. Будет исследована сложность и структура оптимальных схем для ряда функций, встречающихся в приложениях. Будут получены, в частности, оценки высокой степени точности для сложности реализации мультиплексорной функции в некоторых классах схем, описана структура оптимальных и близких к ним контактных схем и схем из функциональных элементов для некоторых симметрических функций и др. Будет разработан ряд новых методов "вложения" схем в различные регулярные структуры (в плоские прямоугольные решетки - топологическую модель СБИС, в единичные кубы и др.). Будет продолжена, в частности, разработка методов реализации функций алгебры логики клеточными схемами различных типов, а также схемами, вложенными в гиперкуб. Будут найдены новые примеры полных схемных базисов, допускающих константные верхние оценки функций Шеннона длины проверяющих тестов при различных типах неисправностей функциональных элементов. Будут получены новые оценки функций Шеннона длины теста при неисправностях на входах схем. Будут созданы модифицированные варианты разработанных методов, ориентированные на решение задач логического и топологического синтеза СБИС.

Разработаны методы эффективной реализации функций алгебры логики (ФАЛ) схемами из некоторых классов, связанных, как правило, с введением определенных ограничений на структуру и параметры схем одного из основных типов. В каждом из этих классов получены новые более точные асимптотические оценки функции Шеннона, которая равна сложности реализации самой сложной ФАЛ от n булевых переменных (БП), n=1,2, …, схемами данного класса. Полученные оценки являются, как правило, либо асимптотическими оценками высокой степени точности (АОВСТ), которые устанавливают поведение функции Шеннона с точностью до асимптотики первого остаточного члена ее «стандартного» асимптотического разложения, либо близкими к ним оценками. Так, получены близкие к АОВСТ оценки функции Шеннона для сложности обобщенных BDD, где выбор одной из двух дуг, исходящих из любой вершины схемы, не являющейся ее стоком, определяется значением приписанной ей базисной ФАЛ, зависящей от входных БП схемы, а число указанных вершин определяет ее сложность. Установлены АОВСТ функции Шеннона для сложности предикатных схем в некоторых новых базисах и АОВСТ функции Шеннона для сложности формул с глубиной альтернирования 3, реализующих ФАЛ из некоторых классов, связанных с грамматиками, имеющими конечное число состояний. Получены АОВСТ функции Шеннона для сложности формул в базисах из функциональных элементов с прямыми и итеративными входами, являющихся итеративными модификациями стандартного базиса. Установлен ряд фактов, показывающих, что получение аналогичных результатов для произвольного базиса является сложной задачей. Разработаны новые более эффективные методы синтеза схем из функциональных элементов (СФЭ) в стандартном базисе с ограничениями на ветвление выходов элементов. Для произвольной квазимультиплексорной ФАЛ получены нетривиальные нижние оценки сложности ее реализации в классах формул и СФЭ стандартного базиса. При этом в некоторых случаях доказаны верхние оценки, близкие к нижним. В модели задержки СФЭ, где задержка базисного элемента положительна и задается произвольно для каждого входа, каждого возможного варианта подключения других элементов к этому входу, а также каждого набора значений остальных входов данного элемента, получены близкие к АОВСТ оценки соответствующей функции Шеннона для задержки ФАЛ. Разработан метод синтеза СФЭ в стандартном базисе с их оптимизацией как по динамической мощности, так и по сложности. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, сложность которой близка к АОВСТ соответствующей функции Шеннона, а динамическая мощность растет линейно по числу переменных исходной ФАЛ. Разработан метод синтеза СФЭ в стандартном базисе с оптимизацией получаемой схемы как по глубине, так и по размерности единичного куба, допускающего ее изоморфное вложение. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, размерность которой отличается от значения соответствующей функции Шеннона не более чем на константу, а глубина растет линейно по числу переменных исходной ФАЛ. Доказано существование некоторых конечных полных базисов, в которых функция Шеннона длины полного проверяющего теста относительно инверсных неисправностей на выходах элементов не превосходит константы, а также установлено, что во всяком конечном полном базисе функция Шеннона длины единичного проверяющего теста относительно константных и инверсных неисправностей на выходах элементов не превосходит константы. Доказано, что для произвольной отличной от константы булевой функции существуют тестопригодные контактные схемы либо с одной дополнительной существенной переменной, либо с одним дополнительным полюсом, которые допускают единичные проверяющие тесты линейной по числу переменных длины. Установлено, что для почти всех булевых функций n переменных существуют двухполюсные контактные схемы с линейной по числу переменных длиной полного проверяющего теста размыкания (замыкания). Получены новые оценки (в ряде случаев асимптотически точные или точные по порядку роста) функций Шеннона длин полного проверяющего и полного диагностического теста относительно различных типов слипаний переменных булевой функции (в частности, линейных, симметрических, монотонных симметрических слипаний), относительно примитивных сдвигов влево входов схем, а также относительно вытесняющих неисправностей входов схем.