МОДЕЛИРОВАНИЕ И АНАЛИЗ ИНФОРМАЦИОННЫХ СИСТЕМ

В статье предлагается метод построения графов сигнальных переходов (STG), которые напрямую отображаются в схемы асинхронной обработки данных. Преимуществом предлагаемого метода является то, что полученные схемы не только неизменны по выходу (output-persistent), но и конформны внешней среде. В других подходах среда задаётся неявно и/или неточно, и поэтому они гарантируют только неизменность по выходу. Конформность можно проверить, если как схема, так и её внешняя среда заданы STG. В качестве примера мы рассматриваем модуль, реализующий функцию 2И. Этот модуль может либо ожидать лог. 1 на обоих входах, либо вычислить функцию, как только придёт хотя бы один 0. Для каждого случая мы составляем отдельный STG (сценарий) и отображаем его в элементы NCL. Чтобы обеспечить такое отображение, мы задаём поведение NCL элементов STG протоколами . Для тракта данных такой STG всегда содержит альтернативные ветви с так называемыми мусорными переключениями на входах элементов. Мусорные переключения на определенном проводе означают, что схема чувствительна к задержке в этом проводе. Игнорирование мусора может привести к нарушению конформности и/или неизменности по выходу. Например, в комбинационной части NCL схем мусор появляется на входах NCL элементов, поэтому эти схемы чувствительны к задержкам.

Рассматривается система из трех связанных в кольцо генераторов с несимметричной нелинейностью и специальной нелинейной связью. Исследуемая система моделирует электрическую цепь, в которой каждый из трех идентичных генераторов представляет собой колебательный контур с нелинейным элементом. Вольт-амперная характеристика этого элемента имеет S-образный характер. Нелинейная связь между генераторами организована так, что имеет близкий к единичному коэффициент передачи в прямом направлении и близкий к нулевому в обратном. Асимптотическими методами сначала изучается задача о решениях, ветвящихся от состояний равновесия, а затем численными методами исследуется исходная система. Изучена зависимость динамики системы от степени несимметричности кубической нелинейности, описывающей характеристику нелинейного элемента.

Выражения со смешанной булевой и целочисленной арифметикой (далее - MBA-выражения, от англ. Mixed Boolean-Arithmetic) от t целочисленных n-битных переменных часто находят применение при обфускации (запутывании) программного кода. Запутывание заключается в замене коротких выражений более длинными эквивалентными выражениями, на исследование которых, как представляется, аналитиком может быть затрачено больше времени. В работе показано, что для упрощения линейных MBA-выражений (сокращения количества слагаемых) может быть применена техника, аналогичная технике декодирования линейных кодов по информационным совокупностям. На основе этой техники в работе построены алгоритмы упрощения линейных MBA-выражений: алгоритм нахождения выражения с минимальным числом слагаемых и алгоритм сокращения числа слагаемых. На основе алгоритма сокращения числа слагаемых построен алгоритм, позволяющий оценить стойкость MBA“=выражения к упрощению. В работе экспериментально оценена зависимость среднего числа слагаемых в линейном MBA-выражении, возвращаемом алгоритмами упрощения, от разрядности n, числа итераций декодирования и мощности набора булевых функций, по которому ищется линейная комбинация с минимальным числом ненулевых коэффициентов. Результаты экспериментов для всех рассмотренных t и n показывают, что если до обфускации линейное MBA-выражение содержало r=1,2,3 слагаемых, то разработанные алгоритмы упрощения с вероятностью, близкой к единице, позволяют по обфусцированному варианту этого выражения найти эквивалентное с числом слагаемых не более r. В этом заключается главное отличие техники декодирования по информационным совокупностям от известных техник упрощения линейных MBA-выражений, в которых целью является сокращение числа слагаемых до не более чем 2t. В работе также установлено, что для случайно сгенерированных линейных MBA-выражений с ростом n среднее число слагаемых в возвращаемом выражении стремится к 2t и не отличается от среднего числа слагаемых в линейном выражении, возвращаемом известными алгоритмами упрощения. Полученные результаты, в частности, позволяют определить t и n, для которых количество слагаемых в упрощенном линейном MBA-выражении в среднем будет не менее заданного.

Среди полных систем булевых функций особый интерес представляют самодостаточные операторы. Они обладают широкой областью применимости и не ограничиваются двухместным случаем. В данной работе формулируются условия, накладываемые на коэффициенты полинома Жегалкина, необходимые и достаточные для того, чтобы полином соответствовал самодостаточному оператору. Рассмотрено полиномиальное представление булевых функций, сохраняющих константу. Показано, что свойства монотонности и линейности не требуют специального рассмотрения при описании самодостаточного оператора. Вводится понятие полинома двойственного остатка, значение которого позволяет определить самодвойственность булевой функции. Доказано, что сохраняющая 0 и 1 или не сохраняющая ни 0, ни 1 булева функция является самодвойственной тогда и только тогда, когда двойственный остаток соответствующего ей полинома Жегалкина равен 0 для любых наборов значений переменных функции. На основании этого факта получена система ведущих коэффициентов. Решение данной системы позволило сформулировать критерий самодвойственности булевой функции, представленной полиномом Жегалкина, накладывающий необходимые и достаточные условия на коэффициенты полинома. Таким образом, показано, что полиномы Жегалкина являются достаточно удобным инструментом при исследовании предполных классов булевых функций.