ИСТИНА

В рамках проекта будет проведена разработка оригинальных эффективных методов реализации «типичных» и «самых сложных» функций алгебры логики (ФАЛ) в ряде классов комбинационных дискретных управляющих систем при определѐнных ограничениях на структуру и параметры схем. С помощью этих методов будут получены оценки, являющиеся, как правило, асимптотическими оценками высокой степени точности (АОВСТ), для сложности «типичных» функций и сложности «самой сложной» функции, то есть функции Шеннона, в указанных классах схем. Будет выполнена разработка методов синтеза и будут установлены асимптотические оценки различной степени точности для задержки (глубины) схем из функциональных элементов (СФЭ) в некоторых моделях, учитывающих особенности процесса распространения сигналов в современных СБИС, а также для динамической активности схем как функционального, так и проводящего типов, моделирующей энергопотребление СБИС. На уровне АОВСТ или близких к ним оценок будет исследовано поведение функции Шеннона для сложности реализации ФАЛ формулами и СФЭ в базисах из элементов с прямыми и итеративными входами. Будет исследовано асимптотическое поведение функции Шеннона для сложности реализации ФАЛ в классе рекурсивных СФЭ с ограниченной глубиной рекурсии и в некоторых более общих моделях программного типа. Асимптотические оценки различной степени точности будут получены для сложности реализации ФАЛ схемами, допускающими вложение в некоторые «регулярные» геометрические структуры (единичные кубы, плоские прямоугольные решетки и др.), причем будет изучена возможность построения схем, оптимальных как по «объемным», так и по «временным» параметрам. Будут получены новые нетривиальные оценки функций Шеннона длин а) диагностических тестов при неисправностях на выходах элементов в СФЭ, б) проверяющих тестов при размыканиях и замыканиях контактов в контактных схемах, в) тестов при размыкаиях и замыканиях контактов в обобщенных итеративных контактных схемах. При этом планируется разработать ряд новых методов синтеза легкотестируемых схем. Как оценки функций Шеннона, так и разрабатываемые методы синтеза схем, имея самостоятельную теоретическую значимость, могут служить подспорьем для специалистов по проектированию, тестированию, верификации и информационной защите интегральных схем.

In the course of project realization, original effective methods of Boolean functions implementation in a range of classes of combinational discrete control systems with additional structural and parametric constraints will be investigated for the “typical” or “hardest” Boolean functions. With the help of these methods new asymptotic bounds (usually with high degree of accuracy) for the complexity of the “typical” or “hardest” Boolean functions (e.i. Shannon’s function) will be obtained in the considered classes of control systems. Synthesis methods will be developed and new asymptotic bounds with different degree of accuracy will be acquired for the delay (depth) of Boolean circuits for some delay models, which accounts for the properties of the signal propagation in model VLSI circuits, and for the switching activity (a parameter, which models dynamic power dissipation) for circuit models of both functional and conductive type. Behavior of Shannon’s function for the complexity of Boolean function implementation with formulae and Boolean circuits with direct and repetitive inputs will be investigated at the level of high accuracy bounds and bounds close to the high accuracy level. Asyptotic behavior of Shannon’s function will be investigated for the class or recursive Boolean circuits with bound recursion depth and for more general models of program type. Asymptotic bounds of different level of accuracy will be obtained for the complexity of Boolean functions’ implementation for circuits, which allow embedment into different regular geometrical structures (e.g. Boolean hypercubes, rectangular lattices and etc.). Furthermore, possibility of constructing “volume” and “time” optimal circuits will be investigated. New nontrivial bounds will be acquired for the cardinality of diagnostic test sets for gates' input faults for Boolean circuits, for diagnostic test sets for breaking and close of contacts in switching circuits and for test for breaking and close of contacts in generalized iterative switching circuits. Furthemore, a range of new synthesis methods for easily testable circuits will be developed. Having independent theoretical value, both bounds for Shannon’s function and developed synthesis methods can be of help for experts in the field of development, testing, verification and security of integrated circuits.

Первое направление проекта (см. п. 4.6) посвящено разработке эффективных методов синтеза схем из некоторых классов как для «типичных» или «самых сложных» дискретных функций, так и для ряда специальных функций, встречающихся в приложениях. В рамках этого направления проекта на базе различных вариантов метода асимптотических оценок высокой степени точности (АОВСТ) будут созданы оригинальные эффективные методы реализации «типичных» и «самых сложных» функций в ряде известных классов дискретных управляющих систем (ДУС) при определенных ограничениях на структуру и параметры схем, а также в некоторых новых классах схем и относительно ряда новых функционалов сложности. С помощью этих методов для сложности «типичных» функций и сложности «самой сложной» функции, то есть функции Шеннона, в указанных классах схем с соответствующими ограничениями будут получены асимптотические оценки, имеющие, как правило, высокую степень точности. Будет проведено исследование на уровне АОВСТ или близких к ним оценок сложности реализации функций из специальных классов, а также некоторых индивидуальных функций, встречающихся в приложениях. В течение всего времени выполнения проекта планируется продолжить начатое ранее (грант РФФИ 15-01-07474) исследование сложности реализации как произвольных функций алгебры логики (ФАЛ), так и ФАЛ из некоторых специальных классов в модели формул и схем из функциональных элементов (СФЭ) над базисом из элементов с «прямыми» и итеративными входами. При этом в 2018 г. предполагается разработать методы синтеза формул в ряде новых базисов указанного вида, в которых функция Шеннона для сложности формул имеет стандартный порядок роста, и с их помощью получить ее АОВСТ. В 2019 году планируется исследовать сложность формул в базисах рассматриваемого вида, итеративное замыкание которых не содержит монотонных ФАЛ, а в 2020 году получить оценки индивидуальной сложности ФАЛ и классов ФАЛ. В течение всего времени выполнения проекта планируется продолжить начатое ранее (грант РФФИ 15-01-07474) исследование задержки реализации ФАЛ в моделях формул и СФЭ над базисами общего и специального вида, а также связи задержки ФАЛ с другими функционалами их сложности в указанных моделях вычислений. В 2018 г. предполагается разработать методы синтеза формул в ряде новых базисов и с их помощью установить АОВСТ или близкие к ним оценки функции Шеннона для задержки формул над данными базисами. В 2019, 2020 годах планируется распространить полученные результаты на более широкие классы базисов, исследовать возможность оптимизации полученных схем как по задержке, так и по сложности. В 2018 г. планируется начать, а в 2019 и 2020 годах продолжить исследование сложности реализации ФАЛ в ряде моделей рекурсивных бинарных программ, вычисляющих ФАЛ. При этом в 2018 г. планируется разработать методы синтеза и установить асимптотическое поведение функции Шеннона для сложности реализации ФАЛ в некоторых классах рекурсивных СФЭ с ограниченной глубиной рекурсии, в 2019 г. распространить эти результаты на ряд классов рекурсивных бинарных программ общего вида, а в 2020 г. получить АОВСТ или близкие к ним оценки рассматриваемой функции Шеннона для некоторых подклассов указанных классов схем. В 2018 г. предполагается продолжить начатое в 2017 г. исследование степени защищенности СФЭ в произвольном базисе, построенных для произвольных ФАЛ с помощью методов синтеза, позволяющих получить АОВСТ, в некоторых специальных моделях раскрытия функциональности. В 2019 и 2020 годах планируется исследовать указанные вопросы в ряде других моделей раскрытия функциональности СФЭ. В течение всего времени выполнения проекта предполагается продолжить начатую ранее (грант 15-01-07474) разработку методов синтеза оптимизированных по динамической активности и, возможно, ряду других параметров таких, как сложность, глубина и статическая активность, схем в некоторых классах схем функционального или проводящего типа. При этом в 2018 г. планируется с помощью данных методов исследовать указанные функционалы сложности для произвольных или «типичных» ФАЛ с оценками отклонений каждого из параметров от значения соответствующей функции Шеннона, а в 2019 и 2020 годах – для некоторых ФАЛ, встречающихся в приложениях. В ходе проекта планируется продолжить начатое в 2017 г. исследование возможности построения таких односторонних гомеоморфных вложений двоичных деревьев подобных формул над двуместными коммутативными и ассоциативными базисами в плоские прямоугольные решетки, которые дают близкие к оптимальным значения как высоты решетки, так и глубины дерева. При этом в 2018 г. планируется уточнить указанные параметры для односторонних вложений и разработать алгоритм построения аналогичных асимптотически оптимальных двусторонних вложений, а 2019 и 2020 годах распространить полученные результаты на некоторые другие классы деревьев и типы вложений. В течение всего времени выполнения проекта планируется продолжить разработку методов построения вложений СФЭ, реализующих произвольные ФАЛ или ФАЛ из специальных классов в единичные кубы (в плоские прямоугольные решетки ограниченной высоты) с оптимизацией размерности куба и глубины СФЭ (соответственно площади решетки). Планируется исследовать сложность реализации ряда специальных ФАЛ в некоторых классах контактных схем и BDD с возможным описанием структуры всех минимальных схем, а также глубину и сложность указанных ФАЛ в некоторых базисах. В рамках второго направления проекта, связанного с тестированием дискретных управляющих систем, планируется продолжить работу над получением нетривиальных оценок функций Шеннона длин тестов (в частности, на уровне точных значений, с точностью до аддитивных констант, на асимптотическом уровне или на уровне порядка роста). Так, в 2018 году планируется получить новые оценки функций Шеннона длин диагностических тестов при неисправностях на выходах элементов в СФЭ в некоторых базисах. Предполагается также получить нетривиальные оценки длин минимальных единичных проверяющих тестов для контактных схем (относительно размыканий и замыканий контактов). При этом в 2018-2020 годах будет продолжено изучение поведения функций Шеннона длин диагностических тестов при неисправностях на выходах элементов в СФЭ в различных базисах. В 2019-2020 годах ожидается также получение новых оценок функций Шеннона длин тестов для обобщенных итеративных контактных схем. Верхние оценки функций Шеннона длины теста предполагается сопровождать разработкой новых методов синтеза легкотестируемых схем.

В первом направлении один проекта его исполнители имеют большой набор методов и результатов, связанных с разработкой методов синтеза и получением асимптотических оценок высокой и близкой к ней степени точности как для различных функций Шеннона, так и для некоторых специальных ФАЛ. Эти методы и результаты составляют задел, на базе которого будут получены ожидаемые результаты направления 1. Основным методом, с помощью которого планируется получать указанные результаты, является метод асимптотических оценок высокой степени точности (АОВСТ) и его модификации. Во втором направлении проекта также имеется целый ряд методов и результатов, связанных с разработкой методов синтеза легкотестируемых схем и получением соответствующих тестов. Эти методы и результаты составляют задел, на базе которого будут получены ожидаемые результаты направления 2.